{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Supersequence LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestSeq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短超串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。</p>\n",
    "\n",
    "<p>返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "big = <code>[7,5,9,0,2,1,3,<strong>5,7,9,1</strong>,1,5,8,8,9,7]\n",
    "small = [1,5,9]</code>\n",
    "<strong>输出: </strong>[7,10]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong>\n",
    "big = <code>[1,2,3]\n",
    "small = [4]</code>\n",
    "<strong>输出: </strong>[]</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>big.length&nbsp;&lt;= 100000</code></li>\n",
    "\t<li><code>1 &lt;= small.length&nbsp;&lt;= 100000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-supersequence-lcci](https://leetcode.cn/problems/shortest-supersequence-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-supersequence-lcci](https://leetcode.cn/problems/shortest-supersequence-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        visit = 0\n",
    "        count = 0\n",
    "        for e in rolls:\n",
    "            visit |= (1 << e)\n",
    "            if visit == (1 << k+1)-2:\n",
    "                count += 1\n",
    "                visit = 0\n",
    "        return count+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        \n",
    "        # 贪心\n",
    "        mark = [0] * (k + 1) # mark[v] 标记v属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)\n",
    "        ans,left = 1,k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        T=(1<<(k+1))-2\n",
    "        cur=0\n",
    "        for r in rolls:\n",
    "            cur |=1<<r\n",
    "            if cur==T:\n",
    "                cur=0\n",
    "                ans+=1\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ret = 1\n",
    "\n",
    "        vis = [0]*(k+1)\n",
    "        left = k\n",
    "\n",
    "        for roll in rolls:\n",
    "            if vis[roll] >= ret:\n",
    "                continue\n",
    "            vis[roll] = ret\n",
    "            left -= 1\n",
    "            if left == 0:\n",
    "                ret += 1\n",
    "                left = k\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [False]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        \n",
    "        for v in rolls:\n",
    "            if not lst[v-1]:\n",
    "                lst[v-1] = True\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    lst = [False]*k\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark_order = [0] * (k+1) #每个元素储存在第几个 1 到 k 的最短子串\n",
    "        res = 0\n",
    "        left = k #判断已经有几个数字被记录 \n",
    "        for roll in rolls:\n",
    "            if(mark_order[roll] == res):\n",
    "                mark_order[roll] += 1\n",
    "                left -= 1\n",
    "            if(left == 0):\n",
    "                res += 1\n",
    "                left = k\n",
    "        \n",
    "        return res + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # 因为判断某个序列是不是给定数组的子序列的过程是个从前往后贪心匹配的过程，所以构造一个不在其中的序列的过程可以看成是在匹配过程中不停反悔的过程，只要能不匹配就不匹配，直到所有可用的字母都被否定过之后才被迫承认匹配上了一个字符，这样就得到了O(n)的解法。\n",
    "        # 构造一个最短的，不在rolls中的子序列\n",
    "        # 匹配一定是从第一个开始，所以出现的晚的好 \n",
    "        # 遍历rolls，找到一个完整的段包含1-k，取最后一个出现的数字，第几段，长度尝试+1\n",
    "                                                # 这个最后的数字在当前段只出现过一次\n",
    "        mark = [0]*(k+1)\n",
    "        ans, left = 1, k#当前子序列长ans, 剩余未出现的数字有k个\n",
    "        for v in rolls:\n",
    "            # print(mark)\n",
    "            if mark[v]<ans: # v已出现的段 mark[v]段，第ans段还没有\n",
    "                mark[v] = ans # 在ans段出现了一个新的数\n",
    "                left -=1 # 当前段剩余未出现的数少一个\n",
    "                if left ==0:# 这个长度的子序列全都有的\n",
    "                    left = k # 清空，记录下一段\n",
    "                    ans += 1 # 进入下一段的计数\n",
    "            # print(ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [0] * (k + 1)\n",
    "        count = 0\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if lst[v] < res:\n",
    "                lst[v] = res\n",
    "                count += 1\n",
    "\n",
    "            if count == k:\n",
    "                res+=1\n",
    "                count = 0\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    ans += 1\n",
    "                    left = k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [False]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        \n",
    "        for v in rolls:\n",
    "            if not lst[v-1]:\n",
    "                lst[v-1] = True\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    lst = [False]*k\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)  # mark[v] 标记 v 属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        n = len(rolls)\n",
    "        ans = 1\n",
    "        cnt = 0\n",
    "        found = [False] * (k+1)\n",
    "        for x in rolls:\n",
    "            if not found[x]:\n",
    "                found[x] = True\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    ans += 1\n",
    "                    cnt = 0\n",
    "                    found = [False] * (k+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [0]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if lst[v-1] < res :\n",
    "                lst[v-1]  = res\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        appears = [0]*(k+1)\n",
    "        appeared = runs = 0\n",
    "        for n in rolls:\n",
    "            if appears[n]: continue\n",
    "            appeared += 1\n",
    "            if appeared == k:\n",
    "                appeared = 0\n",
    "                for i in range(1, k+1):\n",
    "                    appears[i] = 0\n",
    "                runs += 1\n",
    "            else:\n",
    "                appears[n] = 1\n",
    "        return runs + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        m = [0] * (k + 1)\n",
    "        re, cnt = 1, k\n",
    "        for x in rolls:\n",
    "            if m[x] < re:\n",
    "                m[x] = re\n",
    "                cnt -= 1\n",
    "                if (cnt == 0):\n",
    "                    re += 1\n",
    "                    cnt = k\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)  # mark[v] 标记 v 属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        mark = [0] * (k + 1)  # mark[v] 标记 v 属于哪个子段\n",
    "        ans, left = 1, k\n",
    "        for v in rolls:\n",
    "            if mark[v] < ans:\n",
    "                mark[v] = ans\n",
    "                left -= 1\n",
    "                if left == 0:\n",
    "                    left = k\n",
    "                    ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        lst = [0]*k\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        \n",
    "        for v in rolls:\n",
    "            if lst[v-1] < res :\n",
    "                lst[v-1] += 1\n",
    "                cnt += 1\n",
    "                if cnt == k:\n",
    "                    cnt = 0\n",
    "                    res += 1\n",
    "        return res\t\t\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTreeMin:\n",
    "    def __init__(self, n):\n",
    "        self.nums = [0] * (4*n)\n",
    "\n",
    "    # 某个结点的标号node，区间左侧left，区间右侧right，添加的位置idx，添加的值val\n",
    "    def set(self, node, left, right, idx, val):\n",
    "        if left == right:\n",
    "            self.nums[node] = val\n",
    "            return\n",
    "        mid = (right + left) // 2\n",
    "        if idx <= mid:\n",
    "            self.set(2 * node + 1, left, mid, idx, val)\n",
    "        else:\n",
    "            self.set(2 * node + 2, mid + 1, right, idx, val)\n",
    "        self.nums[node] = min(self.nums[2*node+1], self.nums[2*node+2])\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # 首先，如果能得到更长的序列，所以短的一定能覆盖，是具备单调性的\n",
    "        tree = SegTreeMin(k)\n",
    "        for x in rolls[::-1]:\n",
    "            minval = tree.nums[0]\n",
    "            tree.set(node=0, left=0, right=k-1, idx=x-1, val=minval+1)\n",
    "        return 1 + tree.nums[0]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1 \n",
    "        s = set()\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                res += 1 \n",
    "                s.clear()\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # lst = [1]*k\n",
    "        # count1 = 1\n",
    "        # for v in rolls:\n",
    "        #     if lst[v-1] == 1:\n",
    "        #         lst[v-1] = 0\n",
    "        #     if 1 not in lst:\n",
    "        #         lst = [1]*k\n",
    "        #         count1 += 1\n",
    "        # return count1\n",
    "        lst = set()\n",
    "        count1 = 1\n",
    "        for v in rolls:\n",
    "            lst.add(v)\n",
    "            if len(lst) == k:\n",
    "                lst = set()\n",
    "                count1 += 1\n",
    "        return count1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        # 考虑成能找到多少组 (1~k)的段\n",
    "        s = set()\n",
    "        ans = 0\n",
    "        for r in rolls:\n",
    "            s.add(r)\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s.clear()\n",
    "        return ans + 1 # 找到ans个段,可以随意构建ans长度的序列,但ans + 1长度就不行了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s=set()\n",
    "        ans=0\n",
    "        for r in rolls:\n",
    "            s.add(r)\n",
    "            if len(s)==k:\n",
    "                s.clear()\n",
    "                ans+=1\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for v in rolls:\n",
    "            set1.add(v)\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if v not in st:\n",
    "                st.add(v)\n",
    "            if len(st) == k:\n",
    "                res += 1\n",
    "                st.clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans = 1\n",
    "        s = set()\n",
    "        for x in rolls:\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "                if len(s) == k:\n",
    "                    s = set()\n",
    "                    ans += 1\n",
    "        return ans\n",
    "        # mark = [0] * (k + 1)\n",
    "        # ans,left = 1,k\n",
    "        # for v in rolls:\n",
    "        #     if mark[v] < ans:\n",
    "        #         mark[v] = ans\n",
    "        #         left -= 1\n",
    "        #         if left == 0:\n",
    "        #             left = k\n",
    "        #             ans += 1\n",
    "        # return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        dic = set()\n",
    "        ans = 1\n",
    "        for i in range(len(rolls)):\n",
    "            if(rolls[i] not in dic):\n",
    "                dic.add(rolls[i])\n",
    "                if(len(dic) == k):\n",
    "                    ans += 1\n",
    "                    dic = set()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if v not in st:\n",
    "                st.add(v)\n",
    "            if len(st) == k:\n",
    "                res += 1\n",
    "                st = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        dic = set()\n",
    "        ans = 0\n",
    "        for i in range(len(rolls)):\n",
    "            if(rolls[i] not in dic):\n",
    "                dic.add(rolls[i])\n",
    "                if(len(dic) == k):\n",
    "                    ans += 1\n",
    "                    dic = set()\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ans = 1\n",
    "        for x in rolls:\n",
    "            if x not in s:\n",
    "                s.add(x)\n",
    "                if len(s) == k:\n",
    "                    s = set()\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        ret = 0\n",
    "        for x in rolls:\n",
    "            st.add(x)\n",
    "            if len(st) == k:\n",
    "                ret += 1\n",
    "                st.clear()\n",
    "        return ret + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans = 1\n",
    "        pre = set()\n",
    "        for num in rolls:\n",
    "            pre.add(num)\n",
    "            if len(pre) == k:\n",
    "                ans += 1\n",
    "                pre = set()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for v in rolls:\n",
    "            if v <= k:\n",
    "                set1.add(v)\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        ans = 1\n",
    "        s = set()\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for v in rolls:\n",
    "            if v <= k:\n",
    "                set1.add(v)\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ret = 1\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                ret += 1\n",
    "                s = set()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        st = set()\n",
    "        res = 1\n",
    "        for v in rolls:\n",
    "            if v not in st:\n",
    "                st.add(v)\n",
    "            if len(st) == k:\n",
    "                res += 1\n",
    "                st = set()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        s = set()\n",
    "        ans = 1\n",
    "        for x in rolls:\n",
    "            s.add(x)\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "\n",
    "        st = set()\n",
    "        ans = 0 #ans表示能得到所有长度为ans的子序列\n",
    "        for r in rolls:\n",
    "            st.add(r)\n",
    "            if len(st)==k: #这组的数字全了，清空哈希集合，进入下一组\n",
    "                st.clear()\n",
    "                ans+=1\n",
    "        return ans+1 #ans+1就无法保证了\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        n = len(rolls)\n",
    "\n",
    "        i = 0\n",
    "        s = set()\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            s.add(rolls[i])\n",
    "            if len(s) == k:\n",
    "                ans += 1\n",
    "                s = set()\n",
    "            i += 1\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        tmp = set()\n",
    "        count = 0\n",
    "        for v in rolls:\n",
    "            tmp.add(v)\n",
    "            count +=1\n",
    "            if len(tmp) == k:\n",
    "                res += 1\n",
    "                tmp = set()\n",
    "                count = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        vis = set()\n",
    "        for r in rolls:\n",
    "            vis.add(r)\n",
    "            if len(vis) == k:\n",
    "                cnt += 1\n",
    "                vis = set()\n",
    "        return cnt + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "  \n",
    "        s = set()\n",
    "        count = 1\n",
    "        for v in rolls:\n",
    "            if v not in s:\n",
    "                s.add(v)\n",
    "            if len(s) == k:\n",
    "                count += 1\n",
    "                s = set()\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1 = set()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls, k):\n",
    "        res=0\n",
    "        kset=set()\n",
    "        for i in rolls:\n",
    "            kset.add(i)\n",
    "            if len(kset)==k:\n",
    "                res+=1\n",
    "                kset=set()\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1.clear()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls, k):\n",
    "        res=0\n",
    "        kset=set()\n",
    "        for i in rolls:\n",
    "            kset.add(i)\n",
    "            if len(kset)==k:\n",
    "                res+=1\n",
    "                kset=set()\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 1\n",
    "        set1 = set()\n",
    "        for i in range(len(rolls)):\n",
    "            if rolls[i] <= k:\n",
    "                set1.add(rolls[i])\n",
    "            if len(set1) == k:\n",
    "                res += 1\n",
    "                set1 = set()\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSequence(self, rolls: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        set_ = set()\n",
    "        for v in rolls:\n",
    "            set_.add(v)\n",
    "            if len(set_) == k:\n",
    "                res += 1\n",
    "                set_ = set()\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        \n",
    "        dic = collections.Counter(small)\n",
    "        need = len(small)\n",
    "\n",
    "        left,right = 0,0\n",
    "        res = []\n",
    "        min_length = len(big) + 1\n",
    "\n",
    "        for right in range(len(big)):\n",
    "            ch = big[right]\n",
    "            if ch in dic:\n",
    "                if dic[ch] > 0:\n",
    "                    need -= 1\n",
    "                dic[ch] -= 1\n",
    "\n",
    "            while need == 0:\n",
    "                if min_length > right - left + 1:\n",
    "                    min_length = right - left + 1\n",
    "                    res = [left,right]\n",
    "                \n",
    "                ch = big[left]\n",
    "                if ch in dic:\n",
    "                    if dic[ch] >= 0:\n",
    "                        need += 1\n",
    "                    dic[ch] += 1\n",
    "                left += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        l, n = 0, 0\n",
    "        cnt = collections.Counter(small)\n",
    "        res = []\n",
    "        for i, ch in enumerate(big):\n",
    "            if ch not in cnt:\n",
    "                continue\n",
    "            cnt[ch] -= 1\n",
    "            if cnt[ch] == 0:\n",
    "                n += 1\n",
    "            while big[l] not in cnt or cnt[big[l]] < 0:\n",
    "                if big[l] in cnt:\n",
    "                    cnt[big[l]] += 1\n",
    "                l += 1\n",
    "            if n == len(cnt):\n",
    "                if res and i - l < res[1] - res[0]:\n",
    "                    res = [l, i]\n",
    "                elif not res:\n",
    "                    res = [l, i]\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        # n,m = len(big),len(small)\n",
    "        # if m>n:return []\n",
    "        # stack = []\n",
    "        # small = set(small)\n",
    "        # left,right = -1,n\n",
    "        # acc = {}\n",
    "        # for i in range(n):\n",
    "        #     if big[i] not in small:continue\n",
    "        #     if big[i] in acc:\n",
    "        #         x = bisect.bisect_left(stack,acc[big[i]])\n",
    "        #         stack[x:] = stack[x+1:]\n",
    "        #     acc[big[i]] = i\n",
    "        #     stack.append(i)\n",
    "        #     if len(stack)==m:\n",
    "        #         if stack[-1]-stack[0]<right-left:\n",
    "        #             left,right = stack[0],stack[-1]\n",
    "        #         acc.pop(big[stack.pop(0)])\n",
    "        # return [left,right] if right!=n else []\n",
    "\n",
    "\n",
    "        # 滑动窗口\n",
    "        m,n = len(small),len(big)\n",
    "        if m>n:return []\n",
    "        count = collections.defaultdict(int)\n",
    "        for c in small:\n",
    "            count[c]+=1\n",
    "        need = len(small)\n",
    "        left,right = 0,n\n",
    "        star,end = 0,0\n",
    "        minlen = n+1\n",
    "        while end<n:\n",
    "            tmp = big[end]\n",
    "            if tmp in count:\n",
    "                if count[tmp]>0:\n",
    "                    need-=1\n",
    "                count[tmp]-=1\n",
    "            \n",
    "            while need==0:\n",
    "                if end-star<minlen:\n",
    "                    left,right = star,end\n",
    "                    minlen = end-star\n",
    "                tmp = big[star]\n",
    "                if tmp in count:\n",
    "                    if count[tmp]>=0:\n",
    "                        need+=1\n",
    "                    count[tmp]+=1\n",
    "                star+=1\n",
    "            end+=1\n",
    "        return [left,right] if right!=n else []\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        # n,m = len(big),len(small)\n",
    "        # if m>n:return []\n",
    "        # stack = []\n",
    "        # small = set(small)\n",
    "        # left,right = -1,n\n",
    "        # acc = {}\n",
    "        # for i in range(n):\n",
    "        #     if big[i] not in small:continue\n",
    "        #     if big[i] in acc:\n",
    "        #         x = bisect.bisect_left(stack,acc[big[i]])\n",
    "        #         stack[x:] = stack[x+1:]\n",
    "        #     acc[big[i]] = i\n",
    "        #     stack.append(i)\n",
    "        #     if len(stack)==m:\n",
    "        #         if stack[-1]-stack[0]<right-left:\n",
    "        #             left,right = stack[0],stack[-1]\n",
    "        #         acc.pop(big[stack.pop(0)])\n",
    "        # return [left,right] if right!=n else []\n",
    "\n",
    "\n",
    "        # 滑动窗口\n",
    "        m,n = len(small),len(big)\n",
    "        if m>n:return []\n",
    "        count = collections.defaultdict(int)\n",
    "        for c in small:\n",
    "            count[c]+=1\n",
    "        need = len(small)\n",
    "        left,right = 0,n\n",
    "        star,end = 0,0\n",
    "        minlen = n+1\n",
    "        while end<n:\n",
    "            tmp = big[end]\n",
    "            if tmp in count:\n",
    "                if count[tmp]>0:\n",
    "                    need-=1\n",
    "                count[tmp]-=1\n",
    "            \n",
    "            while need==0:\n",
    "                if end-star<minlen:\n",
    "                    left,right = star,end\n",
    "                    minlen = end-star\n",
    "                tmp = big[star]\n",
    "                if tmp in count:\n",
    "                    if count[tmp]>=0:\n",
    "                        need+=1\n",
    "                    count[tmp]+=1\n",
    "                star+=1\n",
    "            end+=1\n",
    "        return [left,right] if right!=n else []\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        # 记录目标数组的出现次数，即需要的个数\n",
    "        target_map = Counter(small)\n",
    "        # 总共需要的个数\n",
    "        total_need = len(small)\n",
    "\n",
    "        # 最终输出结果\n",
    "        min_len = len(big) + 1\n",
    "        start,end = 0,-1\n",
    "\n",
    "        # 肯定无符合的 判断\n",
    "        if len(small) > len(big):\n",
    "            return []\n",
    "\n",
    "        # 初始化滑动窗口\n",
    "        l,r = 0,0\n",
    "        while r < len(big):\n",
    "            new_element = big[r]\n",
    "            if new_element in target_map:\n",
    "                # 如果刚好这个需要的个数>0，即取这个数之后，可以更新总共需要的个数\n",
    "                if target_map[new_element] > 0:\n",
    "                    total_need -= 1\n",
    "                target_map[new_element] -= 1\n",
    "            # 判断当前是否符合题意，如果符合记录\n",
    "            # 并且尝试缩小左指针\n",
    "            while total_need == 0:\n",
    "                if r-l+1 < min_len:\n",
    "                    min_len = r-l+1\n",
    "                    start,end = l,r\n",
    "                drop_element = big[l]\n",
    "                if drop_element in target_map:\n",
    "                    # 如果刚好需要的个数 = 0，即 删掉这个就不符合题意了，total_need需要更新\n",
    "                    if target_map[drop_element] == 0:\n",
    "                        total_need += 1\n",
    "                    target_map[drop_element] += 1\n",
    "\n",
    "                # 尝试缩小左指针\n",
    "                l += 1\n",
    "\n",
    "            r += 1\n",
    "        if end != -1:\n",
    "\n",
    "            return [start,end]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        # n,m = len(big),len(small)\n",
    "        # if m>n:return []\n",
    "        # stack = []\n",
    "        # small = set(small)\n",
    "        # left,right = -1,n\n",
    "        # acc = {}\n",
    "        # for i in range(n):\n",
    "        #     if big[i] not in small:continue\n",
    "        #     if big[i] in acc:\n",
    "        #         x = bisect.bisect_left(stack,acc[big[i]])\n",
    "        #         stack[x:] = stack[x+1:]\n",
    "        #     acc[big[i]] = i\n",
    "        #     stack.append(i)\n",
    "        #     if len(stack)==m:\n",
    "        #         if stack[-1]-stack[0]<right-left:\n",
    "        #             left,right = stack[0],stack[-1]\n",
    "        #         acc.pop(big[stack.pop(0)])\n",
    "        # return [left,right] if right!=n else []\n",
    "\n",
    "\n",
    "        # 滑动窗口\n",
    "        m,n = len(small),len(big)\n",
    "        if m>n:return []\n",
    "        count = collections.defaultdict(int)\n",
    "        for c in small:\n",
    "            count[c]+=1\n",
    "        need = len(small)\n",
    "        left,right = 0,n\n",
    "        star,end = 0,0\n",
    "        minlen = n+1\n",
    "        while end<n:\n",
    "            tmp = big[end]\n",
    "            if tmp in count:\n",
    "                if count[tmp]>0:\n",
    "                    need-=1\n",
    "                count[tmp]-=1\n",
    "            \n",
    "            while need==0:\n",
    "                if end-star<minlen:\n",
    "                    left,right = star,end\n",
    "                    minlen = end-star\n",
    "                tmp = big[star]\n",
    "                if tmp in count:\n",
    "                    if count[tmp]>=0:\n",
    "                        need+=1\n",
    "                    count[tmp]+=1\n",
    "                star+=1\n",
    "            end+=1\n",
    "        return [left,right] if right!=n else []\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        \n",
    "        cnt=collections.Counter(small)\n",
    "        n=len(big)\n",
    "        left,right=0,0\n",
    "        start,end=0,-1\n",
    "        need=len(small)\n",
    "        minlen=n+1\n",
    "        for right in range(n):\n",
    "            ch=big[right]\n",
    "            if ch in cnt:\n",
    "                if cnt[ch]>0:\n",
    "                    need-=1\n",
    "                cnt[ch]-=1\n",
    "            while need==0:\n",
    "                if right-left+1<minlen:\n",
    "                    minlen=right-left+1\n",
    "                    start,end=left,right\n",
    "                ch=big[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch]>=0:\n",
    "                        need+=1\n",
    "                    cnt[ch]+=1\n",
    "                left+=1\n",
    "        if minlen<n+1:\n",
    "            return [start,end]\n",
    "        else: return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\r\n",
    "        i, j = 0, -1\r\n",
    "        cnt = {x: 0 for x in small}  # 记录 [i:j] 中各元素出现次数\r\n",
    "        totcnt = 0\r\n",
    "        # 滑动窗口\r\n",
    "        ans = []\r\n",
    "        while i < len(big) and j < len(big):\r\n",
    "            if totcnt == len(small):  # [i:j] 已包含所有元素\r\n",
    "                if not ans or ans[1] - ans[0] > j - i:\r\n",
    "                    ans = [i, j]\r\n",
    "                if big[i] in cnt:\r\n",
    "                    cnt[big[i]] -= 1\r\n",
    "                    if cnt[big[i]] == 0:\r\n",
    "                        totcnt -= 1\r\n",
    "                i += 1\r\n",
    "            else:  # [i:j] 不包含全部元素\r\n",
    "                j += 1\r\n",
    "                if j < len(big) and big[j] in cnt:\r\n",
    "                    if cnt[big[j]] == 0:\r\n",
    "                        totcnt += 1\r\n",
    "                    cnt[big[j]] += 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(small) > len(big):\n",
    "            return []    \n",
    "\n",
    "        temp = len(big) + 1\n",
    "        need = len(small)           \n",
    "        dic = {}\n",
    "        for i in small:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        res = []\n",
    "        left = right = 0\n",
    "\n",
    "        for right in range(len(big)):\n",
    "            num = big[right]\n",
    "            if num in dic:\n",
    "                if dic[num] > 0:\n",
    "                    need -= 1\n",
    "                dic[num] -= 1\n",
    "        \n",
    "            while need == 0:\n",
    "                if right - left + 1 < temp:\n",
    "                    temp = right - left + 1\n",
    "                    res = [left, right]\n",
    "                num = big[left]\n",
    "                if num in dic:\n",
    "                    if dic[num] == 0:\n",
    "                        need += 1\n",
    "                    dic[num] += 1\n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # binary search will work, over minimum fixed subarray window size in big\n",
    "    # also dynamic sliding window?\n",
    "    # \n",
    "#     def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "#         m,n = len(big), len(small)\n",
    "#         freq_small = Counter(small)\n",
    "#         l = 0\n",
    "#         window = Counter(small)\n",
    "#         res = inf\n",
    "#         i = -1\n",
    "#         j = -1\n",
    "#         for r in range(m):\n",
    "#             #window[big[r]] += 1\n",
    "#             if big[r] in window:\n",
    "#                 window[big[r]] -= 1 # want to get it empty\n",
    "#                 if window[big[r]] == 0: del window[big[r]]\n",
    "\n",
    "#             while not window:\n",
    "#                 #res = min(res, r-l+1)\n",
    "#                 print(window, l,r)\n",
    "#                 if r-l+1 < res:\n",
    "#                     i = l\n",
    "#                     j = r\n",
    "#                     res = r-l+1\n",
    "                \n",
    "#                 if big[l] in freq_small:\n",
    "#                     window[big[l]] += 1\n",
    "                \n",
    "#                 l += 1\n",
    "#         # res is the min window distance...\n",
    "#         # now we can compute the answer greedily using fixed sliding window.\n",
    "#         # OR: just store the real answer inside the loop.\n",
    "#         #return res\n",
    "#         print(res)\n",
    "#         return [i,j] if (i,j) != (-1,-1) else []\n",
    "\n",
    "# 解答错误\n",
    "# 执行用时: 52 ms\n",
    "# Case 1\n",
    "# Case 2\n",
    "# 输入\n",
    "# big =\n",
    "# [842, 336, 777, 112, 789, 801, 922, 874, 634, 121, 390, 614, 179, 565, 740, 672, 624, 130, 555, 714, 9, 950, 887, 375, 312, 862, 304, 121, 360, 579, 937, 148, 614, 885, 836, 842, 505, 187, 210, 536, 763, 880, 652, 64, 272, 675, 33, 341, 101, 673, 995, 485, 16, 434, 540, 284, 567, 821, 994, 174, 634, 597, 919, 547, 340, 2, 512, 433, 323, 895, 965, 225, 702, 387, 632, 898, 297, 351, 936, 431, 468, 694, 287, 671, 190, 496, 80, 110, 491, 365, 504, 681, 672, 825, 277, 138, 778, 851, 732, 176]\n",
    "# small =\n",
    "# [950, 885, 702, 101, 312, 652, 555, 936, 842, 33, 634, 851, 174, 210, 287, 672, 994, 614, 732, 919, 504, 778, 340, 694, 880, 110, 777, 836, 365, 375, 536, 547, 887, 272, 995, 121, 225, 112, 740, 567, 898, 390, 579, 505, 351, 937, 825, 323, 874, 138, 512, 671, 297, 179, 277, 304]\n",
    "# 标准输出\n",
    "# Counter() 0 98\n",
    "# 99\n",
    "# 输出\n",
    "# [0,98]\n",
    "# 预期结果\n",
    "# [2,98]\n",
    "\n",
    "    # NEED counter...\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big), len(small)\n",
    "        freq_small = Counter(small)\n",
    "        l = 0\n",
    "        #window = Counter(small)\n",
    "        counter = n # this is the count of chars in small WE ARE MISSING...\n",
    "        min_length = inf\n",
    "        res = []\n",
    "        \n",
    "        for r in range(m):\n",
    "            #window[big[r]] += 1\n",
    "            if big[r] in freq_small:\n",
    "                freq_small[big[r]] -= 1\n",
    "                if freq_small[big[r]] >= 0: counter -= 1\n",
    "\n",
    "            while counter == 0:\n",
    "                #res = min(res, r-l+1)\n",
    "                # print(window, l,r)\n",
    "                if r-l+1 < min_length:\n",
    "                    res = [l,r]\n",
    "                    min_length = r-l+1\n",
    "                \n",
    "                if big[l] in freq_small:\n",
    "                    freq_small[big[l]] += 1\n",
    "                    if freq_small[big[l]] > 0: counter += 1\n",
    "                \n",
    "                l += 1\n",
    "        # res is the min window distance...\n",
    "        # now we can compute the answer greedily using fixed sliding window.\n",
    "        # OR: just store the real answer inside the loop.\n",
    "        #return res\n",
    "        #print(res)\n",
    "        return res\n",
    "        #return [i,j] if (i,j) != (-1,-1) else []\n",
    "\n",
    "    # binary search, then fixed sliding window\n",
    "    # interesting solution, very similar to dynamic.\n",
    "    # THIS WORKS!!!  but is quite slow\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big), len(small)\n",
    "        l,r = 1,m # DO NOT init l == 0...\n",
    "        # res = []\n",
    "        def check(mid): # returns boolean, and the start index of the first subarray that works!!!\n",
    "            freq_small = Counter(small)\n",
    "            counter = 0\n",
    "            for i in range(m):\n",
    "                if big[i] in freq_small:\n",
    "                    freq_small[big[i]] -= 1\n",
    "                    if freq_small[big[i]] >= 0: counter += 1\n",
    "                if i >= mid-1:\n",
    "                    if counter == n: return True, i-(mid-1), i\n",
    "                    # print(i,mid,m)\n",
    "                    if big[i-(mid-1)] in freq_small:\n",
    "                        freq_small[big[i-(mid-1)]] += 1\n",
    "                        if freq_small[big[i-(mid-1)]] > 0: counter -= 1\n",
    "            return False, -1, -1\n",
    "\n",
    "        while l < r:\n",
    "            mid = l+(r-l)//2\n",
    "            \n",
    "            bool_, i,j = check(mid)\n",
    "            #print(l,r,bool_)\n",
    "            if bool_:\n",
    "                r = mid\n",
    "                #res = [i,j]\n",
    "            else:\n",
    "                l = mid+1\n",
    "       #  print(l)\n",
    "        ok,i,j = check(l)\n",
    "        return [i,j] if ok else []\n",
    "        #return [check(l)[1], check(l)[2]] if check(l)[0] else []\n",
    "\n",
    "    # cleaner counter dynamic sliding window. more inutiive to init counter = 0, add 1 if we add the right char. sub 1 if taking out...\n",
    "    # INTERVIEW READY\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big), len(small)\n",
    "        freq_small = Counter(small)\n",
    "        l = 0\n",
    "        counter = 0\n",
    "        min_length = inf\n",
    "        res = []\n",
    "        for r in range(m):\n",
    "            if big[r] in freq_small:\n",
    "                freq_small[big[r]] -= 1\n",
    "                if freq_small[big[r]] >= 0: counter += 1\n",
    "\n",
    "            while counter == n:\n",
    "                if r-l+1 < min_length:\n",
    "                    res = [l,r]\n",
    "                    min_length = r-l+1\n",
    "                \n",
    "                if big[l] in freq_small:\n",
    "                    freq_small[big[l]] += 1\n",
    "                    if freq_small[big[l]] > 0: counter -= 1\n",
    "                \n",
    "                l += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # binary search will work, over minimum fixed subarray window size in big\n",
    "    # also dynamic sliding window?\n",
    "    # \n",
    "#     def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "#         m,n = len(big), len(small)\n",
    "#         freq_small = Counter(small)\n",
    "#         l = 0\n",
    "#         window = Counter(small)\n",
    "#         res = inf\n",
    "#         i = -1\n",
    "#         j = -1\n",
    "#         for r in range(m):\n",
    "#             #window[big[r]] += 1\n",
    "#             if big[r] in window:\n",
    "#                 window[big[r]] -= 1 # want to get it empty\n",
    "#                 if window[big[r]] == 0: del window[big[r]]\n",
    "\n",
    "#             while not window:\n",
    "#                 #res = min(res, r-l+1)\n",
    "#                 print(window, l,r)\n",
    "#                 if r-l+1 < res:\n",
    "#                     i = l\n",
    "#                     j = r\n",
    "#                     res = r-l+1\n",
    "                \n",
    "#                 if big[l] in freq_small:\n",
    "#                     window[big[l]] += 1\n",
    "                \n",
    "#                 l += 1\n",
    "#         # res is the min window distance...\n",
    "#         # now we can compute the answer greedily using fixed sliding window.\n",
    "#         # OR: just store the real answer inside the loop.\n",
    "#         #return res\n",
    "#         print(res)\n",
    "#         return [i,j] if (i,j) != (-1,-1) else []\n",
    "\n",
    "# 解答错误\n",
    "# 执行用时: 52 ms\n",
    "# Case 1\n",
    "# Case 2\n",
    "# 输入\n",
    "# big =\n",
    "# [842, 336, 777, 112, 789, 801, 922, 874, 634, 121, 390, 614, 179, 565, 740, 672, 624, 130, 555, 714, 9, 950, 887, 375, 312, 862, 304, 121, 360, 579, 937, 148, 614, 885, 836, 842, 505, 187, 210, 536, 763, 880, 652, 64, 272, 675, 33, 341, 101, 673, 995, 485, 16, 434, 540, 284, 567, 821, 994, 174, 634, 597, 919, 547, 340, 2, 512, 433, 323, 895, 965, 225, 702, 387, 632, 898, 297, 351, 936, 431, 468, 694, 287, 671, 190, 496, 80, 110, 491, 365, 504, 681, 672, 825, 277, 138, 778, 851, 732, 176]\n",
    "# small =\n",
    "# [950, 885, 702, 101, 312, 652, 555, 936, 842, 33, 634, 851, 174, 210, 287, 672, 994, 614, 732, 919, 504, 778, 340, 694, 880, 110, 777, 836, 365, 375, 536, 547, 887, 272, 995, 121, 225, 112, 740, 567, 898, 390, 579, 505, 351, 937, 825, 323, 874, 138, 512, 671, 297, 179, 277, 304]\n",
    "# 标准输出\n",
    "# Counter() 0 98\n",
    "# 99\n",
    "# 输出\n",
    "# [0,98]\n",
    "# 预期结果\n",
    "# [2,98]\n",
    "\n",
    "    # NEED counter...\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big), len(small)\n",
    "        freq_small = Counter(small)\n",
    "        l = 0\n",
    "        #window = Counter(small)\n",
    "        counter = n # this is the count of chars in small WE ARE MISSING...\n",
    "        min_length = inf\n",
    "        res = []\n",
    "        \n",
    "        for r in range(m):\n",
    "            #window[big[r]] += 1\n",
    "            if big[r] in freq_small:\n",
    "                freq_small[big[r]] -= 1\n",
    "                if freq_small[big[r]] >= 0: counter -= 1\n",
    "\n",
    "            while counter == 0:\n",
    "                #res = min(res, r-l+1)\n",
    "                # print(window, l,r)\n",
    "                if r-l+1 < min_length:\n",
    "                    res = [l,r]\n",
    "                    min_length = r-l+1\n",
    "                \n",
    "                if big[l] in freq_small:\n",
    "                    freq_small[big[l]] += 1\n",
    "                    if freq_small[big[l]] > 0: counter += 1\n",
    "                \n",
    "                l += 1\n",
    "        # res is the min window distance...\n",
    "        # now we can compute the answer greedily using fixed sliding window.\n",
    "        # OR: just store the real answer inside the loop.\n",
    "        #return res\n",
    "        #print(res)\n",
    "        return res\n",
    "        #return [i,j] if (i,j) != (-1,-1) else []\n",
    "\n",
    "    # binary search, then fixed sliding window\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big), len(small)\n",
    "        l,r = 1,m # DO NOT init l == 0...\n",
    "        # res = []\n",
    "        def check(mid): # returns boolean, and the start index of the first subarray that works!!!\n",
    "            freq_small = Counter(small)\n",
    "            counter = 0\n",
    "            for i in range(m):\n",
    "                if big[i] in freq_small:\n",
    "                    freq_small[big[i]] -= 1\n",
    "                    if freq_small[big[i]] >= 0: counter += 1\n",
    "                if i >= mid-1:\n",
    "                    if counter == n: return True, i-(mid-1), i\n",
    "                    # print(i,mid,m)\n",
    "                    if big[i-(mid-1)] in freq_small:\n",
    "                        freq_small[big[i-(mid-1)]] += 1\n",
    "                        if freq_small[big[i-(mid-1)]] > 0: counter -= 1\n",
    "            return False, -1, -1\n",
    "\n",
    "        while l < r:\n",
    "            mid = l+(r-l)//2\n",
    "            \n",
    "            bool_, i,j = check(mid)\n",
    "            #print(l,r,bool_)\n",
    "            if bool_:\n",
    "                r = mid\n",
    "                #res = [i,j]\n",
    "            else:\n",
    "                l = mid+1\n",
    "       #  print(l)\n",
    "        ok,i,j = check(l)\n",
    "        return [i,j] if ok else []\n",
    "        #return [check(l)[1], check(l)[2]] if check(l)[0] else []\n",
    "\n",
    "    # cleaner counter dynamic sliding window. more inutiive to init counter = 0, add 1 if we add the right char. sub 1 if taking out...\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big), len(small)\n",
    "        freq_small = Counter(small)\n",
    "        l = 0\n",
    "        counter = 0\n",
    "        min_length = inf\n",
    "        res = []\n",
    "        for r in range(m):\n",
    "            if big[r] in freq_small:\n",
    "                freq_small[big[r]] -= 1\n",
    "                if freq_small[big[r]] >= 0: counter += 1\n",
    "\n",
    "            while counter == n:\n",
    "                if r-l+1 < min_length:\n",
    "                    res = [l,r]\n",
    "                    min_length = r-l+1\n",
    "                \n",
    "                if big[l] in freq_small:\n",
    "                    freq_small[big[l]] += 1\n",
    "                    if freq_small[big[l]] > 0: counter -= 1\n",
    "                \n",
    "                l += 1\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#python滑动窗口超时\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        i=0\n",
    "        n=len(big)\n",
    "        needmap=dict()\n",
    "        needcnt=0\n",
    "        for num in small:\n",
    "            needmap[num]=1\n",
    "            needcnt+=1\n",
    "        small=set(small)\n",
    "        minlen=math.inf\n",
    "        res=[]\n",
    "        for j in range(n):\n",
    "            if (big[j] in small):\n",
    "                needmap[big[j]]-=1\n",
    "                if needmap[big[j]]>=0:\n",
    "                    needcnt-=1\n",
    "            while(needcnt==0):\n",
    "                if j-i+1<minlen:\n",
    "                    minlen=j-i+1\n",
    "                    res=[i,j]\n",
    "                if big[i] in needmap:\n",
    "                    if needmap[big[i]]==0:\n",
    "                        needcnt+=1\n",
    "                    needmap[big[i]]+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    i+=1               \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        # 滑动窗口\n",
    "        small = set(small)\n",
    "        left  = 0 \n",
    "        min_len = inf\n",
    "        ans = []\n",
    "        # for right,v in enumerate(big):\n",
    "        #     if v in small:\n",
    "        #         counter.add(v)\n",
    "        #     while len(counter) == len(small):\n",
    "        #         if right - left + 1 < min_len:\n",
    "        #             min_len = right - left + 1\n",
    "        #             ans = [left,right]\n",
    "        #         # big[left] 在counter中删除了，但是在区间big[left:right]中还是会存在一个big[left]\n",
    "        #         if big[left] in small:\n",
    "        #             counter.remove(big[left])\n",
    "        #         left += 1\n",
    "        # return ans\n",
    "        counter = collections.Counter(small)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = len(small)                   # 记录需要匹配到的元素总数【need=0表示匹配到了】\n",
    "        for right,v in enumerate(big):\n",
    "            if v in counter:\n",
    "                if counter[v] > 0:\n",
    "                    need -= 1\n",
    "                counter[v] -= 1\n",
    "            while need == 0:\n",
    "                if right - left + 1 < min_len:\n",
    "                    min_len = right - left + 1\n",
    "                    ans = [left,right]\n",
    "                # big[left] 在counter中删除了，但是在区间big[left:right]中还是会存在一个big[left]\n",
    "                if big[left] in counter:\n",
    "                    if counter[big[left]] >= 0:\n",
    "                        need += 1\n",
    "                    counter[big[left]] += 1\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(small)>len(big):\n",
    "            return []\n",
    "        cnt=collections.Counter(small)\n",
    "        need=len(small)\n",
    "\n",
    "        n=len(big)\n",
    "        res=[]\n",
    "        left,right=0,0\n",
    "        min_len=n+1\n",
    "\n",
    "        for right in range(n):\n",
    "            num=big[right]\n",
    "            if num in cnt:\n",
    "                if cnt[num]>0:\n",
    "                    need-=1\n",
    "                cnt[num]-=1\n",
    "            \n",
    "\n",
    "            while need==0:\n",
    "                if right-left+1<min_len:\n",
    "                    min_len=right-left+1\n",
    "                    res=[left,right]\n",
    "                \n",
    "                num=big[left]\n",
    "\n",
    "                if num in cnt:\n",
    "                    if cnt[num]>=0:\n",
    "                        need+=1\n",
    "                    cnt[num]+=1\n",
    "                left+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        pool = set(small)\n",
    "        target = len(pool)\n",
    "        res = [None, None]\n",
    "        left, right = 0, 0\n",
    "        cnt = Counter()\n",
    "        now = 0\n",
    "\n",
    "\n",
    "        while right < len(big):\n",
    "            if big[right] in pool:\n",
    "                cnt[big[right]] += 1\n",
    "                if cnt[big[right]] == 1:\n",
    "                    now += 1\n",
    "            right += 1\n",
    "            \n",
    "            while now >= target:\n",
    "                if res == [None, None] or right - left < res[1] - res[0] + 1:\n",
    "                    res[0], res[1] = left, right-1\n",
    "                if big[left] in pool:\n",
    "                    cnt[big[left]] -= 1\n",
    "                    if cnt[big[left]] == 0:\n",
    "                        now -= 1\n",
    "                left += 1\n",
    "        \n",
    "        return [] if res == [None, None] else res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import Counter\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "            if len(small) > len(big):\n",
    "                return []   \n",
    "\n",
    "            need=dict(Counter(small))\n",
    "            \n",
    "            l,r=0,0\n",
    "            start,end=0,len(big)+1\n",
    "            l_need=len(small)\n",
    "\n",
    "            for r,ele in enumerate(big):\n",
    "                if ele in need:\n",
    "                    if need[ele]>0:\n",
    "                        l_need-=1\n",
    "                    need[ele]-=1\n",
    "                while l_need==0:\n",
    "                    if r-l<end-start:\n",
    "                        start,end=l,r\n",
    "                    t=big[l]\n",
    "                    if t in need:\n",
    "                        if need[t]==0:\n",
    "                            l_need+=1\n",
    "                        need[t]+=1\n",
    "                    l+=1   \n",
    "            return [] if end==len(big)+1  else [start,end]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        begin = 0\n",
    "        windowElem = Counter()\n",
    "        small = set(small)\n",
    "        for end, elem in enumerate(big):\n",
    "            if elem in small:\n",
    "                windowElem[elem] += 1\n",
    "            while len(windowElem) == len(small):\n",
    "                if len(ans) == 0 or (end - begin < ans[1] - ans[0]) or (end - begin == ans[1] - ans[0] and begin < ans[0]):\n",
    "                    ans = [begin, end]\n",
    "                if big[begin] in windowElem:\n",
    "                    windowElem[big[begin]] -= 1\n",
    "                if windowElem[big[begin]] == 0:\n",
    "                    del windowElem[big[begin]]\n",
    "                begin += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import Counter\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "            if len(small) > len(big):\n",
    "                return []   \n",
    "\n",
    "            need=dict(Counter(small))\n",
    "            \n",
    "            l,r=0,0\n",
    "            start,end=0,len(big)+1\n",
    "            l_need=len(small)\n",
    "\n",
    "            for r,ele in enumerate(big):\n",
    "                if ele in need:\n",
    "                    if need[ele]>0:\n",
    "                        l_need-=1\n",
    "                    need[ele]-=1\n",
    "                while l_need==0:\n",
    "                    if r-l<end-start:\n",
    "                        start,end=l,r\n",
    "                    t=big[l]\n",
    "                    if t in need:\n",
    "                        if need[t]>=0:\n",
    "                            l_need+=1\n",
    "                        need[t]+=1\n",
    "                    l+=1   \n",
    "            return [] if end==len(big)+1  else [start,end]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n = len(small)\n",
    "        s = set(small)\n",
    "        cnt = Counter()\n",
    "        j = ans = 0\n",
    "        minn = inf\n",
    "        for i, x in enumerate(big):\n",
    "            if x in s:\n",
    "                cnt[x] += 1\n",
    "            if len(cnt) == n:\n",
    "                while big[j] not in s or cnt[big[j]] > 1:\n",
    "                    if big[j] in s:\n",
    "                        cnt[big[j]] -= 1\n",
    "                    j += 1\n",
    "                t = i - j + 1\n",
    "                if t < minn:\n",
    "                    minn = t\n",
    "                    ans = j\n",
    "        return [ans, ans+minn-1] if minn < inf else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(big)<len(small):\n",
    "            return []\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        need,window = defaultdict(int),defaultdict(int)\n",
    "        left,right = 0,0\n",
    "        index = []\n",
    "        need_small = False\n",
    "        valid_num = 0\n",
    "        min_length = len(big) + 1\n",
    "        for i in small:\n",
    "            need[i] += 1\n",
    "\n",
    "        while right < len(big):\n",
    "            # print(\"right = \",right)\n",
    "            c = big[right]\n",
    "            right += 1\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid_num += 1\n",
    "            # print(\"window = \",window)\n",
    "            while valid_num == len(small):\n",
    "                if min_length > right - left:\n",
    "                    min_length = right - left\n",
    "                    index = [left,right-1]\n",
    "                d = big[left]\n",
    "                if d in need:\n",
    "                    if need[d] == window[d]:\n",
    "                        valid_num -= 1\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "        # print(\"left,right = \",left,right)\n",
    "        # print(\"index = \",index)\n",
    "        return index\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n = len(big)\n",
    "        m = len(small)\n",
    "        left, right = 0, 0\n",
    "        min_l, min_r = 0, n\n",
    "        s = set(small)\n",
    "        d = defaultdict(int)\n",
    "        cnt = 0\n",
    "        while right < n:\n",
    "            if big[right] in s:\n",
    "                if d[big[right]] == 0:\n",
    "                    cnt += 1\n",
    "                d[big[right]] += 1\n",
    "                if cnt == m:\n",
    "                    while big[left] not in d or d[big[left]] > 1:\n",
    "                        if big[left] in d:\n",
    "                            d[big[left]] -= 1\n",
    "                        left += 1\n",
    "                    if min_r - min_l > right - left:\n",
    "                        min_l = left\n",
    "                        min_r = right\n",
    "                    d[big[left]] -= 1\n",
    "                    cnt -= 1\n",
    "                    left += 1\n",
    "            right += 1\n",
    "        return [min_l, min_r] if min_r != n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "#         n=len(big)\n",
    "#         min_len=9999\n",
    "#         index_lst=[]#保存起始终点下表的数组\n",
    "#         for i in range(n):\n",
    "#             tmp=[]\n",
    "#             j=i\n",
    "#             while j<n:\n",
    "#                 if big[j] in small:\n",
    "#                     tmp.append(big[j])\n",
    "#                 if len(list(set(tmp)))>=len(small) :#防止big数组有重复导致走不下去\n",
    "#                     break\n",
    "#                 j += 1\n",
    "#             if len(big[i:j+1])>=len(small) and all(si in big[i:j+1] for si in small):\n",
    "#                 min_len=min(min_len,len(big[i:j+1]))\n",
    "#                 index_lst.append([i, j])\n",
    "#         for ls in index_lst:\n",
    "#             if ls[1]-ls[0]+1==min_len:\n",
    "#                 return [ls[0],ls[1]]\n",
    "#         return []\n",
    "class Solution:\n",
    "\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "\n",
    "        a=[];s=set(small);slow=0;n=len(big);d=dict() ;cha=n+1\n",
    "\n",
    "        for f,v in enumerate(big):\n",
    "\n",
    "            if v in s:\n",
    "\n",
    "                d[v]=d.setdefault(v,0)+1\n",
    "\n",
    "                if len(s)==len(d): \n",
    "\n",
    "                    #开始准备slow右移动 \n",
    "\n",
    "                    while big[slow] not in s or d[big[slow]]>1:\n",
    "\n",
    "                        if big[slow] in s:\n",
    "\n",
    "                            d[big[slow]]-=1\n",
    "\n",
    "                        slow+=1\n",
    "\n",
    "                   \n",
    "\n",
    "                    if (t:=f-slow+1)<cha:\n",
    "\n",
    "                        cha,a=t,[slow,f]\n",
    "\n",
    "                    del d[big[slow]]\n",
    "\n",
    "                    slow+=1\n",
    "\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(small) > len(big):\n",
    "            return []    \n",
    "\n",
    "        temp = len(big) + 1\n",
    "        need = len(small)           \n",
    "        dic = {}\n",
    "        for i in small:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] += 1\n",
    "        res = []\n",
    "        left = right = 0\n",
    "\n",
    "        for right in range(len(big)):\n",
    "            num = big[right]\n",
    "            if num in dic:\n",
    "                if dic[num] > 0:\n",
    "                    need -= 1\n",
    "                dic[num] -= 1\n",
    "        \n",
    "            while need == 0:\n",
    "                if right - left + 1 < temp:\n",
    "                    temp = right - left + 1\n",
    "                    res = [left, right]\n",
    "                num = big[left]\n",
    "                if num in dic:\n",
    "                    if dic[num] == 0:\n",
    "                        need += 1\n",
    "                    dic[num] += 1\n",
    "                left += 1\n",
    "            print(res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big),len(small)\n",
    "        small = set(small)\n",
    "        cnt = inf\n",
    "        ans = 0\n",
    "        record = {}\n",
    "        l = r = 0\n",
    "        while r < m:\n",
    "            cur = big[r]\n",
    "            if cur in small:\n",
    "                record[cur] = record.get(cur,0) + 1\n",
    "            r += 1\n",
    "            while len(record) == n:\n",
    "                if r-l < cnt:\n",
    "                    cnt = r-l\n",
    "                    ans = l\n",
    "                pre = big[l]\n",
    "                if pre in small:\n",
    "                    if record[pre] == 1:\n",
    "                        del record[pre]\n",
    "                    else:\n",
    "                        record[pre] -= 1\n",
    "                l += 1\n",
    "                if l == m-n-1:\n",
    "                    break\n",
    "        if cnt != inf:\n",
    "            return [ans,cnt+ans-1]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        dict_small=Counter(small)\n",
    "\n",
    "        dict_={}\n",
    "        start=0\n",
    "        min_len=float('inf')\n",
    "        res=[]\n",
    "        def isContain(dict_A,dict_B):\n",
    "            for each in dict_B:\n",
    "                if each not in dict_A or (each in dict_A and dict_A[each]<dict_B[each]):\n",
    "                    return False\n",
    "            return True\n",
    "        for end in range(len(big)):\n",
    "            if big[end] in dict_small:\n",
    "                dict_[big[end]]=dict_.get(big[end],0)+1\n",
    "            while isContain(dict_,dict_small):\n",
    "                if min_len>end- start+1:\n",
    "                    min_len=end-start+1\n",
    "                    res=[start,end]\n",
    "                if big[start] in dict_:\n",
    "                    dict_[big[start]]-=1\n",
    "                start+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        import collections\n",
    "        needCnt = len(small)\n",
    "        if len(big) < needCnt: return []\n",
    "        dic = collections.defaultdict(int)\n",
    "        for k in small:\n",
    "            dic[k] += 1\n",
    "        needCnt = len(small)\n",
    "        res = [0, float('inf')]\n",
    "        left = 0\n",
    "        for right, c in enumerate(big):\n",
    "            if dic[c] > 0:\n",
    "                needCnt -= 1\n",
    "            dic[c] -= 1\n",
    "            if needCnt == 0:\n",
    "                while True:\n",
    "                    if dic[big[left]] == 0:\n",
    "                        break\n",
    "                    else:\n",
    "                        dic[big[left]] += 1\n",
    "                        left += 1\n",
    "                if right - left < res[1] - res[0]:\n",
    "                    res = [left, right]\n",
    "                needCnt += 1\n",
    "                dic[big[left]] += 1\n",
    "                left += 1\n",
    "        return [] if res[1] > len(big) else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "\n",
    "        need = defaultdict(int)\n",
    "        window = defaultdict(int)\n",
    "        for val in small:\n",
    "            need[val] += 1\n",
    "        # print(need)\n",
    "        n = len(big)\n",
    "        left, right = 0, 0\n",
    "        valid = 0\n",
    "        start, lens = 0, float('inf')\n",
    "        while right < n:\n",
    "            add = big[right]\n",
    "            right += 1\n",
    "            if add in need:\n",
    "                window[add] += 1\n",
    "                if need[add] == window[add]:\n",
    "                    valid += 1\n",
    "            while valid == len(need):\n",
    "                if lens > right - left:\n",
    "                    lens = right - left\n",
    "                    start = left\n",
    "                    end = right\n",
    "                delv = big[left]\n",
    "                left += 1\n",
    "                if delv in need:\n",
    "                    if need[delv] == window[delv]:\n",
    "                        valid -= 1\n",
    "                    window[delv] -= 1\n",
    "        # print(lens)\n",
    "        return [] if lens == float('inf') else [start, end-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        s = set(small)\n",
    "        tmp = dict()\n",
    "        i = 0\n",
    "        left = 0\n",
    "        right = len(big)-1\n",
    "        ok = 0\n",
    "\n",
    "        for j in range(len(big)):\n",
    "            if big[j] in s:\n",
    "                if big[j] not in tmp:\n",
    "                    tmp[big[j]] = 0\n",
    "                tmp[big[j]] += 1\n",
    "            while len(tmp) == len(s):\n",
    "                ok = 1\n",
    "                if j-i < right-left:\n",
    "                    left, right = i, j\n",
    "                if big[i] in tmp:\n",
    "                    tmp[big[i]] -= 1\n",
    "                    if tmp[big[i]] == 0:\n",
    "                        del tmp[big[i]]\n",
    "                i += 1\n",
    "        return [left, right] if ok else []\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(big) < len(small):\n",
    "            return []\n",
    "\n",
    "        need, window = collections.defaultdict(int), collections.defaultdict(int)\n",
    "        for c in small:\n",
    "            need[c] += 1\n",
    "\n",
    "        left, right = 0, 0\n",
    "        valid = 0\n",
    "        start, length = 0, float(\"inf\")\n",
    "        while right < len(big):\n",
    "            c = big[right]\n",
    "            right += 1\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if need[c] == window[c]:\n",
    "                    valid += 1\n",
    "            while valid == len(need):\n",
    "                if right - left < length:\n",
    "                    start = left\n",
    "                    length = right - left\n",
    "                d = big[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if need[d] == window[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "        return [start, start + length - 1] if length != float(\"inf\") else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        left = right = 0\n",
    "        need = len(small)\n",
    "        start, end = 0,0\n",
    "        minlen = len(big) + 1\n",
    "        cnt = collections.Counter(small)\n",
    "        # cnt = {key:value for key, value in zip(small,[1]*len(small))}\n",
    "        print(cnt)\n",
    "\n",
    "        for right in range(len(big)):\n",
    "            n = big[right]\n",
    "            if n in cnt:\n",
    "                if cnt[n] > 0:\n",
    "                    need -= 1\n",
    "                cnt[n] -= 1\n",
    "                \n",
    "            while need==0:\n",
    "                n = big[left]\n",
    "                if (right+1-left) < minlen:\n",
    "                   start, end = left, right\n",
    "                   minlen = right+1-left\n",
    "                if n in cnt:\n",
    "                    cnt[n] += 1\n",
    "                    if cnt[n] > 0:\n",
    "                        need += 1\n",
    "\n",
    "                left += 1\n",
    "        \n",
    "        return [start, end] if start|end else []\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        need=len(small)\n",
    "        cnt=Counter(small)\n",
    "        n=len(big)\n",
    "\n",
    "        print(cnt)\n",
    "        l=0\n",
    "        r=0\n",
    "        ansl=-1\n",
    "        ansr=-1\n",
    "        ans=len(big)+1\n",
    "        while r<n:\n",
    "            ch=big[r]\n",
    "            if ch in cnt:\n",
    "                if cnt[ch]>=1:\n",
    "                    need-=1\n",
    "                cnt[ch]-=1\n",
    "                #print(ch,need,l,r)\n",
    "                while need==0 and l<n:\n",
    "                    if r-l+1<ans:\n",
    "                        ans=r-l+1\n",
    "                        ansl=l\n",
    "                        ansr=r\n",
    "                        #print(\"ans\",l,r,ans)\n",
    "                    lch=big[l]\n",
    "                    if lch in cnt:\n",
    "                        cnt[lch]+=1\n",
    "                        if cnt[lch]>=1:\n",
    "                            need+=1\n",
    "                    l+=1\n",
    "                    #print(ch,need,l,r)\n",
    "            r+=1\n",
    "        if ansl!=-1:\n",
    "            return [ansl,ansr]\n",
    "        else:\n",
    "            return []\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "    l, r = 0, 0\n",
    "    al = len(big)\n",
    "    s = set(small)\n",
    "    rec = {}\n",
    "    rl = al + 1\n",
    "    ret = []\n",
    "    while r < al:\n",
    "      v = big[r]\n",
    "      if v in s:\n",
    "        rec[v] = rec.get(v, 0) + 1\n",
    "        if len(rec) == len(s):\n",
    "          while len(rec) == len(s):\n",
    "            lv = big[l]\n",
    "            if lv in s:\n",
    "              if 1 == rec[lv]:\n",
    "                break\n",
    "              else:\n",
    "                rec[lv] -= 1\n",
    "            l += 1\n",
    "          nl = r - l + 1\n",
    "          if nl < rl:\n",
    "            rl = nl\n",
    "            # print(f\"find {rec} {l}->{r}\")\n",
    "            ret =[l, r]\n",
    "      r += 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        d = defaultdict(int)\n",
    "        s_set = set(small)\n",
    "        left = 0\n",
    "        result_left = 0\n",
    "        result_length = 100001\n",
    "        for idx in range(len(big)):\n",
    "            num = big[idx]\n",
    "            if num not in s_set:\n",
    "                continue\n",
    "            d[num] += 1\n",
    "            while left <= idx:\n",
    "                if big[left] not in s_set:\n",
    "                    left += 1\n",
    "                    continue\n",
    "                if d[big[left]] > 1:\n",
    "                    d[big[left]] -= 1\n",
    "                    left += 1\n",
    "                    continue\n",
    "                if len(d) == len(s_set):\n",
    "                    tmp_length = idx - left\n",
    "                    if tmp_length < result_length:\n",
    "                        result_length = tmp_length\n",
    "                        result_left = left\n",
    "                break\n",
    "\n",
    "        if result_length == 100001:\n",
    "            return []\n",
    "        return [result_left, result_left + result_length]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        smallSet = set(small)\n",
    "        counter = defaultdict(int)\n",
    "        n = len(small)\n",
    "        ans = []\n",
    "        left = 0\n",
    "        for i in range(len(big)):\n",
    "            if big[i] in smallSet:\n",
    "                counter[big[i]]+=1\n",
    "            if len(counter)==n:\n",
    "                while big[left] not in counter or (big[left] in counter and counter[big[left]]-1>0):\n",
    "                    if big[left] in counter:\n",
    "                        counter[big[left]]-=1\n",
    "                    left+=1\n",
    "                if not ans or i-left<ans[1]-ans[0]:\n",
    "                    ans = [left,i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big, small):\n",
    "        n = len(big)\n",
    "        m = len(small)\n",
    "        small = sorted(small)\n",
    "        if n == 0 or m == 0:\n",
    "            return []\n",
    "        num2idx = {}\n",
    "        inc = [1]*m\n",
    "        include_c = [0]*m\n",
    "        for i in range(m):\n",
    "            num2idx[small[i]] = i\n",
    "        start = end = -1\n",
    "        min_start = min_end = n+1\n",
    "        min_len = n+1\n",
    "        p_start = -1\n",
    "        p_end = p_start + 1\n",
    "        cnt = m\n",
    "        while p_start < n and p_end < n:\n",
    "            while p_end < n:\n",
    "                # print(p_end)\n",
    "                if big[p_end] not in num2idx.keys():\n",
    "                    p_end += 1\n",
    "                    continue\n",
    "                id = num2idx[big[p_end]]\n",
    "                if include_c[id] == 0:\n",
    "                    cnt -= 1\n",
    "                include_c[id] += 1\n",
    "                # inc[id] = 0\n",
    "                if cnt == 0:\n",
    "                    if (p_end - p_start) < min_len:\n",
    "                        min_start = p_start + 1\n",
    "                        min_end = p_end\n",
    "                        min_len = p_end - p_start\n",
    "                    # print(p_start, p_end)\n",
    "                    break\n",
    "                p_end += 1\n",
    "            p_start += 1\n",
    "            while cnt == 0 and p_start < p_end:\n",
    "                if big[p_start] in num2idx.keys():\n",
    "                    id = num2idx[big[p_start]]\n",
    "                    include_c[id] -= 1\n",
    "                    if include_c[id] == 0:\n",
    "                        cnt += 1\n",
    "                if cnt == 0:\n",
    "                    if (p_end - p_start) < min_len:\n",
    "                        min_start = p_start + 1\n",
    "                        min_end = p_end\n",
    "                        min_len = p_end - p_start\n",
    "                    p_start += 1\n",
    "            p_end += 1\n",
    "        # print(min_start, min_end, min_len)\n",
    "        return [min_start, min_end] if min_start < n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        small_set = set(small)\n",
    "        ans = []\n",
    "        l = 0\n",
    "        subdict = {}\n",
    "        for r,n in enumerate(big):\n",
    "            if n in small_set:\n",
    "                if n in subdict:\n",
    "                    subdict[n] += 1\n",
    "                else:\n",
    "                    subdict[n] = 1\n",
    "            while len(subdict) == len(small) or (ans and ans[1]-ans[0] <= r-l):\n",
    "                if not ans or ans[1]-ans[0] > r-l:\n",
    "                    ans = [l,r]\n",
    "                if big[l] in small_set:\n",
    "                    if subdict[big[l]] == 1:\n",
    "                        del subdict[big[l]]\n",
    "                    else:\n",
    "                        subdict[big[l]] -= 1\n",
    "                l += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n = len(big)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        small_set = set(small)\n",
    "        small_freq = {}\n",
    "        shortest_range = []\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            if big[i] in small_set:\n",
    "                if big[i] not in small_freq:\n",
    "                    small_freq[big[i]] = 1\n",
    "                else:\n",
    "                    small_freq[big[i]] += 1\n",
    "            while len(small_freq) == len(small):\n",
    "                temp_len = i - left + 1\n",
    "                if (\n",
    "                    len(shortest_range) == 0\n",
    "                    or temp_len < shortest_range[1] - shortest_range[0] + 1\n",
    "                ):\n",
    "                    shortest_range = [left, i]\n",
    "                if big[left] in small_set:\n",
    "                    if small_freq[big[left]] == 1:\n",
    "                        small_freq.pop(big[left])\n",
    "                    else:\n",
    "                        small_freq[big[left]] -= 1\n",
    "                left += 1\n",
    "        return shortest_range"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]: \n",
    "        from collections import defaultdict\n",
    "        need = defaultdict(int)\n",
    "        window = defaultdict(int)\n",
    "        for i in small:\n",
    "            need[i] += 1\n",
    "        right, left = 0, 0\n",
    "        valid = 0\n",
    "        result = []\n",
    "        length = float(\"inf\")\n",
    "        while right < len(big):\n",
    "            key = big[right]\n",
    "            right += 1\n",
    "            if key in need:\n",
    "                window[key] += 1\n",
    "                if window[key] == need[key]:\n",
    "                    valid += 1\n",
    "            while valid == len(need):\n",
    "                if right - left < length:\n",
    "                    length = right - left\n",
    "                    result = [left, right - 1]\n",
    "                key_2 = big[left]\n",
    "                left += 1\n",
    "                if key_2 in need:\n",
    "                    window[key_2] -= 1\n",
    "                    if window[key_2] < need[key_2]:\n",
    "                        valid -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        window = {}\n",
    "        need = {}\n",
    "        for x in small:\n",
    "            need[x] = need.get(x, 0) + 1\n",
    "        \n",
    "        valid, left, right = 0, 0, 0\n",
    "        result_left, result_right = 0, 0\n",
    "        min_l = 10 ** 7\n",
    "        while right < len(big):\n",
    "            c = big[right]\n",
    "            right += 1\n",
    "            if need.get(c, 0) > 0:\n",
    "                window[c] = window.get(c, 0) + 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "                \n",
    "            while valid == len(need):\n",
    "                if right - left < min_l:\n",
    "                    min_l = right - left\n",
    "                    result_left = left\n",
    "                    result_right = right - 1\n",
    "                d = big[left]\n",
    "                if need.get(d, 0) > 0:\n",
    "                    if window[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] = window.get(d) - 1\n",
    "                left += 1\n",
    "        return [] if min_l == 10 ** 7 else [result_left, result_right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        m,n = len(big),len(small)\n",
    "        small = set(small)\n",
    "        cnt = inf\n",
    "        ans = 0\n",
    "        record = {}\n",
    "        l = r = 0\n",
    "        while r < m:\n",
    "            cur = big[r]\n",
    "            if cur in small:\n",
    "                record[cur] = record.get(cur,0) + 1\n",
    "            r += 1\n",
    "            while len(record) == n:\n",
    "                if r-l < cnt:\n",
    "                    cnt = r-l\n",
    "                    ans = l\n",
    "                pre = big[l]\n",
    "                if pre in small:\n",
    "                    if record[pre] == 1:\n",
    "                        del record[pre]\n",
    "                    else:\n",
    "                        record[pre] -= 1\n",
    "                l += 1\n",
    "                if m-l < n:\n",
    "                    return [ans,cnt+ans-1]\n",
    "        if cnt != inf:\n",
    "            return [ans,cnt+ans-1]\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        window = Counter()\n",
    "        need = Counter()\n",
    "        valid = 0\n",
    "        left = 0\n",
    "        st = 0\n",
    "        length = float(inf)\n",
    "        for s in small:\n",
    "            need[s] += 1\n",
    "        for right in range(len(big)):\n",
    "            c = big[right]\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "            while(valid == len(need) and left <= right):\n",
    "                if right - left + 1 < length:\n",
    "                    length = right - left + 1\n",
    "                    st = left\n",
    "                d = big[left]\n",
    "                if d in need:\n",
    "                    window[d] -= 1\n",
    "                    if window[d] < need[d]:\n",
    "                        valid -= 1\n",
    "                left += 1\n",
    "        if length == float(inf):\n",
    "            return []\n",
    "        return [st, st+length-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1,2,3]\n",
    "[2]\n",
    "[1,2,3]\n",
    "[2,3]\n",
    "\n",
    "[7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]\n",
    "[1,5,9]\n",
    "[1,2,3]\n",
    "[4]\n",
    "\n",
    "big.length <= 100000\n",
    "1 <= small.length <= 100000\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if not small or not big:\n",
    "            return []\n",
    "\n",
    "        # Map each character in the small array to the number of times it appears\n",
    "        small_count = Counter(small)\n",
    "        required = len(small_count)\n",
    "        # Define a counter for the current window to count the occurrences of each character\n",
    "        window_count = Counter()\n",
    "\n",
    "        l, r = 0, 0\n",
    "        formed = 0\n",
    "        min_len = float('inf')\n",
    "        min_window = (0, 0)\n",
    "\n",
    "        # Start sliding the window\n",
    "        while r < len(big):\n",
    "            character = big[r]\n",
    "            # If the character is part of the small array, add it to the window count\n",
    "            if character in small_count:\n",
    "                window_count[character] += 1\n",
    "                if window_count[character] == small_count[character]:\n",
    "                    formed += 1\n",
    "\n",
    "            # Try to contract the window if all characters are present\n",
    "            while l <= r and formed == required:\n",
    "                character = big[l]\n",
    "                # Save the smallest window until now\n",
    "                if r - l + 1 < min_len:\n",
    "                    min_len = r - l + 1\n",
    "                    min_window = (l, r)\n",
    "\n",
    "                # The character at the position pointed by the `l` pointer is no longer part of the window\n",
    "                if character in small_count:\n",
    "                    window_count[character] -= 1\n",
    "                    if window_count[character] < small_count[character]:\n",
    "                        formed -= 1\n",
    "\n",
    "                l += 1\n",
    "\n",
    "            r += 1\n",
    "\n",
    "        # Return the smallest window indices or an empty array if no such window exists\n",
    "        return list(min_window) if min_len != float('inf') else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n,m = len(big),len(small)\n",
    "        if m>n:return []\n",
    "        stack = []\n",
    "        small = set(small)\n",
    "        left,right = -1,n\n",
    "        acc = {}\n",
    "        for i in range(n):\n",
    "            if big[i] not in small:continue\n",
    "            if big[i] in acc:\n",
    "                x = bisect.bisect_left(stack,acc[big[i]])\n",
    "                stack[x:] = stack[x+1:]\n",
    "            acc[big[i]] = i\n",
    "            stack.append(i)\n",
    "            if len(stack)==m:\n",
    "                if stack[-1]-stack[0]<right-left:\n",
    "                    left,right = stack[0],stack[-1]\n",
    "                acc.pop(big[stack.pop(0)])\n",
    "        return [left,right] if right!=n else []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n,m = len(big),len(small)\n",
    "        if m>n:return []\n",
    "        stack = []\n",
    "        small = set(small)\n",
    "        left,right = -1,n\n",
    "        acc = {}\n",
    "        for i in range(n):\n",
    "            if big[i] not in small:continue\n",
    "            if big[i] in acc:\n",
    "                x = bisect.bisect_left(stack,acc[big[i]])\n",
    "                stack[x:] = stack[x+1:]\n",
    "            acc[big[i]] = i\n",
    "            stack.append(i)\n",
    "            if len(stack)==m:\n",
    "                if stack[-1]-stack[0]<right-left:\n",
    "                    left,right = stack[0],stack[-1]\n",
    "                acc.pop(big[stack.pop(0)])\n",
    "        return [left,right] if right!=n else []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n,m = len(big),len(small)\n",
    "        if m>n:return []\n",
    "        stack = []\n",
    "        small = set(small)\n",
    "        left,right = -1,n\n",
    "        acc = {}\n",
    "        for i in range(n):\n",
    "            if big[i] not in small:continue\n",
    "            if big[i] in acc:\n",
    "                x = bisect.bisect_left(stack,acc[big[i]])\n",
    "                stack[x:] = stack[x+1:]\n",
    "            acc[big[i]] = i\n",
    "            stack.append(i)\n",
    "            if len(stack)==m:\n",
    "                if stack[-1]-stack[0]<right-left:\n",
    "                    left,right = stack[0],stack[-1]\n",
    "                acc.pop(big[stack.pop(0)])\n",
    "        return [left,right] if right!=n else []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        short, long, minLength = {}, {}, 100001\n",
    "        left, right = -1, -1\n",
    "        for value in small:\n",
    "            short[value] = 1\n",
    "        stack = deque()\n",
    "        n = len(big)\n",
    "        for j in range(n):\n",
    "            if big[j] in short:\n",
    "                stack.append(j)\n",
    "                if big[j] not in long:\n",
    "                    long[big[j]] = 1\n",
    "                else:\n",
    "                    long[big[j]] += 1\n",
    "                if len(long)==len(short):\n",
    "                    while stack:\n",
    "                        if long[big[stack[0]]]>1:\n",
    "                            long[big[stack[0]]] -= 1\n",
    "                            stack.popleft()\n",
    "                        else:\n",
    "                            if j - stack[0] + 1 < minLength:\n",
    "                                minLength = j - stack[0] + 1\n",
    "                                left, right = stack[0], j\n",
    "                            break\n",
    "        return [left, right] if left!=-1 and right!=-1 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: list[int], small: list[int]) -> list[int]:\n",
    "        if set(small) <= set(big):\n",
    "            pass\n",
    "        else:\n",
    "            return []\n",
    "        small_list = collections.Counter(small)\n",
    "        left = 0\n",
    "        n = 0\n",
    "        list_end = []\n",
    "        for right, ch in enumerate(big):\n",
    "            if ch not in small_list:\n",
    "                continue\n",
    "            small_list[ch] -= 1\n",
    "            if small_list[ch] == 0:\n",
    "                n += 1\n",
    "            while big[left] not in small_list or small_list[big[left]] < 0:\n",
    "                if small_list[big[left]] < 0:\n",
    "                    small_list[big[left]] += 1\n",
    "                left += 1\n",
    "            if n == len(small_list):\n",
    "                if not list_end or (list_end[1] - list_end[0]) > right - left:\n",
    "                    list_end = []\n",
    "                    list_end.append(left)\n",
    "                    list_end.append(right)\n",
    "        return list_end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        maps = collections.defaultdict(int)\n",
    "        mapb = collections.defaultdict(int)\n",
    "        sets = set(small)\n",
    "        for s in small:\n",
    "            maps[s] += 1\n",
    "\n",
    "        left = 0\n",
    "        res = []\n",
    "        for right in range(len(big)):\n",
    "            if big[right] in sets:\n",
    "                mapb[big[right]] += 1\n",
    "\n",
    "            while left<= right and len(mapb.keys()) == len(small):\n",
    "                if res == [] or right - left + 1< res[1] - res[0] + 1:\n",
    "                    res = [left, right]\n",
    "                if big[left] in sets:\n",
    "                    mapb[big[left]] -= 1\n",
    "                    if mapb[big[left]] == 0:\n",
    "                        mapb.pop(big[left])\n",
    "\n",
    "                left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        checker = {val: [] for val in small}\n",
    "        result = [len(big), tuple()]\n",
    "        small_cache = set(small)\n",
    "        for i in range(result[0]):\n",
    "            if big[i] in small_cache:\n",
    "                checker[big[i]].append(i)\n",
    "        for k, v in checker.items():\n",
    "            if not checker[k]:\n",
    "                return tuple()\n",
    "        cache = [checker[val].pop(0) for val in small]\n",
    "        small_cache = len(small_cache)\n",
    "        while True:\n",
    "            cmax = max(cache)\n",
    "            cmin = min(cache)\n",
    "            if cmax - cmin < result[0]:\n",
    "                result[0] = cmax - cmin\n",
    "                result[1] = (cmin, cmax)\n",
    "                if result[0] == small_cache:\n",
    "                    return result[1]\n",
    "            i = cache.index(cmin)\n",
    "            if not checker[small[i]]:\n",
    "                return result[-1]\n",
    "            cache[i] = checker[small[i]].pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        import collections\n",
    "        cnt = collections.Counter(small)\n",
    "        print(cnt)\n",
    "        l = 0\n",
    "        n = 0\n",
    "        ans = []\n",
    "        for r,ch in enumerate(big):\n",
    "            if ch not in cnt:   #不在cnt 继续\n",
    "                continue\n",
    "            cnt[ch] -= 1         #在cnt\n",
    "            if cnt[ch] == 0:\n",
    "                n += 1          #统计n\n",
    "            while big[l] not in cnt or cnt[big[l]] < 0: #移动左指针：big[l]不在cnt，或者big[l]出现不止一次\n",
    "                if cnt[big[l]] < 0:\n",
    "                    cnt[big[l]] += 1    #如果出现不止一次， 左指针右移，并加一\n",
    "                l += 1\n",
    "            if n == len(cnt):          #如果符合题目条件：\n",
    "                if not ans or (ans[1]-ans[0]) > r - l:   #找最小串\n",
    "                    ans = []\n",
    "                    ans.append(l)\n",
    "                    ans.append(r)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        checker = {val: [] for val in small}\n",
    "        result = [len(big), tuple()]\n",
    "        small_set = set(small)\n",
    "        for i in range(result[0]):\n",
    "            if big[i] in small_set:\n",
    "                checker[big[i]].append(i)\n",
    "        for k, v in checker.items():\n",
    "            if not checker[k]:\n",
    "                return []\n",
    "        cache = [checker[val].pop(0) for val in small]\n",
    "        while True:\n",
    "            if max(cache) - min(cache) < result[0]:\n",
    "                result[0] = max(cache) - min(cache)\n",
    "                result[1] = (min(cache), max(cache))\n",
    "                if result[0] == len(small):\n",
    "                    return result[1]\n",
    "            if count == 0:\n",
    "                break\n",
    "            i = cache.index(min(cache))\n",
    "            if not checker[small[i]]:\n",
    "                return result[-1]\n",
    "            cache[i] = checker[small[i]].pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        book = [0] * (max(big + small) + 1)\n",
    "        i = nonZeros = 0\n",
    "        for num in small:\n",
    "            book[num] += 1\n",
    "            if book[num] == 1:\n",
    "                nonZeros += 1\n",
    "        \n",
    "        ans = []\n",
    "        minLen = inf\n",
    "        for j in range(len(big)):\n",
    "            flag = 0\n",
    "            book[big[j]] -= 1\n",
    "            if not book[big[j]]:\n",
    "                nonZeros -= 1\n",
    "            while not nonZeros:\n",
    "                flag = 1\n",
    "                book[big[i]] += 1\n",
    "                if book[big[i]] == 1:\n",
    "                    nonZeros += 1\n",
    "                i += 1\n",
    "            if flag and (l := j - i) < minLen:\n",
    "                minLen = l\n",
    "                ans = [i - 1, j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        book = [0] * (max(big + small) + 1)\n",
    "        i = nonZeros = 0\n",
    "        for num in small:\n",
    "            book[num] += 1\n",
    "            nonZeros += book[num] == 1\n",
    "        \n",
    "        ans = []\n",
    "        minLen = inf\n",
    "        for j in range(len(big)):\n",
    "            flag = 0\n",
    "            book[big[j]] -= 1\n",
    "            if not book[big[j]]:\n",
    "                nonZeros -= 1\n",
    "            while not nonZeros:\n",
    "                flag = 1\n",
    "                book[big[i]] += 1\n",
    "                if book[big[i]] == 1:\n",
    "                    nonZeros += 1\n",
    "                i += 1\n",
    "            if flag and (l := j - i) < minLen:\n",
    "                minLen = l\n",
    "                ans = [i - 1, j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        t=[]\n",
    "        \n",
    "        a={}\n",
    "        for i in small:\n",
    "            a[i]=0\n",
    "        b={}\n",
    "        cal=len(small)\n",
    "        lon=len(big)\n",
    "        q=0\n",
    "        m=lon+1\n",
    "        i=0\n",
    "        j=0\n",
    "        print(a,i,j,cal)\n",
    "        while j<lon:\n",
    "            while j<lon:\n",
    "                if big[j] in a:\n",
    "                    if big[j] in b:\n",
    "                        b[big[j]]+=1\n",
    "                    else:\n",
    "                        b[big[j]]=1\n",
    "                        q+=1\n",
    "                j+=1\n",
    "                if q==cal:\n",
    "                    if j-i<m:\n",
    "                        m=j-i\n",
    "                        t=[i,j-1]\n",
    "                    break\n",
    "                print(i,j)\n",
    "            \n",
    "            # print(i,j,q)\n",
    "            while True:\n",
    "                if big[i] in a:\n",
    "                    if b[big[i]]>1:\n",
    "                        b[big[i]]-=1\n",
    "                    else:\n",
    "                        q-=1\n",
    "                        b.pop(big[i])\n",
    "                i+=1\n",
    "                if q<cal:\n",
    "                    break\n",
    "                elif q==cal:\n",
    "                    if j-i<m:\n",
    "                        m=j-i\n",
    "                        t=[i,j-1]\n",
    "            # print(i,j,q)\n",
    "        return t\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        # 统计小数组中各元素出现的次数\n",
    "        count = collections.Counter(small)\n",
    "        # 记录还需要找的元素个数\n",
    "        missing = len(small)\n",
    "        left, right = 0, 0\n",
    "        res = []\n",
    "        # 开始遍历大数组\n",
    "        while right < len(big):\n",
    "            # 如果当前数在小数组中出现过，则将其出现次数减1\n",
    "            if count[big[right]] > 0:\n",
    "                missing -= 1\n",
    "            count[big[right]] -= 1\n",
    "            right += 1\n",
    "            # 如果当前找到了小数组中所有元素，则开始缩小左边界\n",
    "            while missing == 0:\n",
    "                # 如果当前子数组比之前找到的更短，则更新结果\n",
    "                if not res or right - left < res[1] - res[0]:\n",
    "                    res = [left, right]\n",
    "                count[big[left]] += 1\n",
    "                # 如果当前缩小左边界后会导致小数组中某个元素缺失，则更新missing\n",
    "                if count[big[left]] > 0:\n",
    "                    missing += 1\n",
    "                left += 1\n",
    "        if res:\n",
    "            res[1] -=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        need = collections.Counter(small)\n",
    "        needCount = len(small)\n",
    "        res = (0, float('inf'))\n",
    "        i = 0\n",
    "        for j, c in enumerate(big):\n",
    "            if need[c] > 0:\n",
    "                needCount -= 1\n",
    "            need[c] -= 1\n",
    "            if not needCount:\n",
    "                while need[big[i]]:\n",
    "                    need[big[i]] += 1\n",
    "                    i += 1\n",
    "                if j-i < res[1]-res[0]:\n",
    "                    res = (i, j)\n",
    "                needCount += 1\n",
    "                need[big[i]] += 1\n",
    "                i += 1\n",
    "        return [] if res[1] > len(big) else res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        count = len(small)\n",
    "        d = collections.defaultdict(int)\n",
    "        for i in range(len(small)):\n",
    "            d[small[i]] += 1\n",
    "        res = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        l = len(big)+1\n",
    "        while left <= right < len(big):\n",
    "            if d[big[right]] > 0:\n",
    "                count -= 1\n",
    "            d[big[right]] -= 1\n",
    "            right += 1\n",
    "            while count == 0:\n",
    "                if right-left < l:\n",
    "                    l = right-left\n",
    "                    res = [left,right-1]\n",
    "                if d[big[left]] == 0:\n",
    "                    count += 1\n",
    "                d[big[left]] += 1\n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        n=len(big)\n",
    "        lookup=collections.Counter(small)\n",
    "        counter=len(small)\n",
    "    \n",
    "        start=end=0\n",
    "        min_len=float(\"inf\")\n",
    "        res=[]\n",
    "        while end<n:\n",
    "            if lookup[big[end]]>0:\n",
    "                counter-=1\n",
    "            lookup[big[end]]-=1\n",
    "            end+=1\n",
    "            while counter==0:\n",
    "                if end-start<min_len:\n",
    "                    res=[start,end-1]\n",
    "                    min_len=end-start\n",
    "                if lookup[big[start]] == 0:\n",
    "                    counter += 1\n",
    "                lookup[big[start]] += 1\n",
    "                start += 1     \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(small)>len(big):\n",
    "            return []\n",
    "        need = len(small)\n",
    "        cnt = collections.defaultdict(int)\n",
    "        for num in small:\n",
    "            cnt[num] += 1\n",
    "        left = right = 0\n",
    "        min_len = len(big)+1\n",
    "        res = []\n",
    "        for right, num in enumerate(big):\n",
    "            if cnt[num]>0:\n",
    "                need -= 1\n",
    "            cnt[num] -= 1\n",
    "            if need == 0:\n",
    "                while True:\n",
    "                    num = big[left]\n",
    "                    if cnt[num] == 0:\n",
    "                        break\n",
    "                    left += 1\n",
    "                    cnt[num] += 1\n",
    "\n",
    "                if right-left+1<min_len:\n",
    "                    min_len = right-left+1\n",
    "                    res = [left, right]\n",
    "\n",
    "                cnt[big[left]] += 1    \n",
    "                left += 1\n",
    "                need += 1            \n",
    "\n",
    "        return res if min_len!=len(big)+1 else[]               \n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        smallSet = set(small)\n",
    "        unique = len(small)\n",
    "        cnt = collections.defaultdict(int)\n",
    "\n",
    "        l = 0\n",
    "        minLen = 2 ** 31 - 1\n",
    "        pos = [-1, -1]\n",
    "        for r in range(len(big)):\n",
    "            cnt[big[r]] += 1\n",
    "            if cnt[big[r]] == 1 and big[r] in smallSet:\n",
    "                unique -= 1\n",
    "            while unique == 0:\n",
    "                if r - l + 1 < minLen:\n",
    "                    minLen = r - l + 1\n",
    "                    pos = [l, r]\n",
    "                if cnt[big[l]] == 1 and big[l] in smallSet:\n",
    "                    unique += 1\n",
    "                cnt[big[l]] -= 1\n",
    "                l += 1\n",
    "        return [] if pos[0] == -1 else pos\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if not big: return []\n",
    "        if not small: return big[0]\n",
    "        #1 维护hashmap, counter, res\n",
    "        hashmap = collections.Counter(small)\n",
    "        counter = len(small)\n",
    "        res = []\n",
    "        min_len = len(big) + 1\n",
    "        # for i in set(small):\n",
    "        #     hashmap[i] += 1\n",
    "        \n",
    "        #2 左右指针\n",
    "        l = 0\n",
    "        for r in range(len(big)):\n",
    "            #4 判断是否在small\n",
    "            if hashmap[big[r]] > 0:\n",
    "                counter -= 1\n",
    "            # 正负\n",
    "            hashmap[big[r]] -= 1\n",
    "            r += 1\n",
    "            while 0 == counter:\n",
    "                #5 res\n",
    "                if min_len > r - l:\n",
    "                    min_len = r - l\n",
    "                    res = [l, r-1]\n",
    "                \n",
    "                #6 left\n",
    "                if hashmap[big[l]] == 0:\n",
    "                    counter += 1\n",
    "                hashmap[big[l]] += 1\n",
    "                l += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def update(self, min_pos, max_pos, res, pos1, pos2):\n",
    "        if max_pos - min_pos < res:\n",
    "            res = max_pos - min_pos\n",
    "            pos1 = min_pos\n",
    "            pos2 = max_pos\n",
    "        return res, pos1, pos2\n",
    "\n",
    "    def shortestSeq(self, big: list[int], small: list[int]) -> list[int]:\n",
    "        min_pos = None\n",
    "        pos_arr = {i: None for i in small}\n",
    "        res = 10**9 # 最小长度\n",
    "        pos1 = -1 # 起始\n",
    "        pos2 = -1 # 结束\n",
    "        success = False # 至少找到\n",
    "        cnt = 0 # 成功找到几个\n",
    "        value_set = []\n",
    "\n",
    "        for idx,num in enumerate(big):\n",
    "            if num in pos_arr:\n",
    "                # 在small数组中是否还存在未找到的\n",
    "                if pos_arr[num] == None:\n",
    "                    cnt += 1\n",
    "                    if cnt == len(small):\n",
    "                        success = True\n",
    "\n",
    "                # 维护min_pos\n",
    "                if pos_arr[num] != None and pos_arr[num] == min_pos:\n",
    "                    value_set = value_set[1:]\n",
    "                    p, v = value_set[0]\n",
    "                    while  p != pos_arr[v]:\n",
    "                        value_set = value_set[1:]\n",
    "                        p, v  = value_set[0]\n",
    "                \n",
    "                pos_arr[num] = idx\n",
    "                value_set.append((idx , num))\n",
    "\n",
    "                if len(pos_arr) != 0:\n",
    "                    min_pos = value_set[0][0]\n",
    "\n",
    "                if success:\n",
    "                    res, pos1, pos2 = self.update(min_pos, idx, res, pos1, pos2) # 更新\n",
    "        \n",
    "        if success:\n",
    "            return [pos1, pos2]\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        if len(big) < len(small):return []\n",
    "        bn = len(big)\n",
    "        small = set(small)\n",
    "        counter = defaultdict(int)\n",
    "        cur = set()\n",
    "        \n",
    "        res = [0, bn]\n",
    "        i = 0\n",
    "        while i < bn and big[i] not in small:\n",
    "            i += 1\n",
    "        j = i\n",
    "        while j < bn:\n",
    "            if big[j] in small:\n",
    "                counter[big[j]] += 1\n",
    "                cur.add(big[j])\n",
    "                if len(cur) == len(small):\n",
    "                    while i < j and (big[i] not in counter or counter[big[i]] > 1):\n",
    "                        if big[i] in counter: counter[big[i]] -= 1\n",
    "                        i += 1\n",
    "                    if res[1] - res[0] > j - i:\n",
    "                        res = [i, j]\n",
    "            j += 1\n",
    "        return res if len(cur) == len(small) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        targetset = defaultdict(int)\n",
    "        count = 0\n",
    "        for _ch in small:\n",
    "            targetset[_ch] += 1\n",
    "            count += 1\n",
    "        tmpset = targetset.copy()\n",
    "        left = 0\n",
    "        for right in range(len(big)):\n",
    "            if tmpset[big[right]] > 0:\n",
    "                count -= 1\n",
    "            if big[right] in tmpset:\n",
    "                tmpset[big[right]] -= 1\n",
    "            while count == 0:\n",
    "                if big[left] in tmpset:\n",
    "                    if tmpset[big[left]] == 0:\n",
    "                        count += 1\n",
    "                    tmpset[big[left]] += 1\n",
    "\n",
    "                if not res or right - left < res[1] - res[0] or (\n",
    "                        right - left == res[1] - res[0] and left < res[0]):\n",
    "                    res = [left, right]\n",
    "                left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        import collections\n",
    "        counters = collections.Counter(small)\n",
    "        sub_seq = collections.defaultdict(int)\n",
    "\n",
    "        left = 0\n",
    "        right = 0\n",
    "        res = []\n",
    "\n",
    "        if big is None or small is None:\n",
    "            return []\n",
    "        if len(big) < len(small):\n",
    "            return []\n",
    "\n",
    "        def contains(a, b):\n",
    "            if len(a) < len(b):\n",
    "                return False\n",
    "            for ele in b:\n",
    "                if a[ele] < b[ele]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while right < len(big):\n",
    "            sub_seq[big[right]] += 1\n",
    "            while contains(sub_seq, counters):\n",
    "                if not res or right - left < res[1] - res[0]:\n",
    "                    res = [left, right]\n",
    "                sub_seq[big[left]] -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        cnt=collections.Counter(small)\n",
    "        print(cnt)\n",
    "        #需要维护的变量\n",
    "        small_len=math.inf\n",
    "        ans=[]\n",
    "        #滑动窗口的起止\n",
    "        start=0\n",
    "        for end in range(len(big)):\n",
    "            #更新需要维护的变量\n",
    "            if big[end] in cnt.keys():\n",
    "                cnt[big[end]]-=1\n",
    "            while all(x<=0 for x in cnt.values()):\n",
    "                if end-start+1<small_len:\n",
    "                    small_len=min(small_len,end-start+1)\n",
    "                    ans=[start,end]\n",
    "                if big[start] in cnt.keys():\n",
    "                    cnt[big[start]]+=1\n",
    "                start+=1\n",
    "        if not ans:return []\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        count_small = Counter(small)\n",
    "        count_big = defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "        cnt, min_len = 0, float('inf')\n",
    "        res = []\n",
    "        while right < len(big):\n",
    "            count_big[big[right]] += 1\n",
    "            if count_big.get(big[right]) == count_small.get(big[right]):\n",
    "                cnt += 1\n",
    "            # while是符合条件  if再通过left缩短子串区间\n",
    "            while cnt == len(count_small):\n",
    "                if right - left + 1 < min_len:\n",
    "                    start = left\n",
    "                    end = right\n",
    "                    min_len = right - left + 1\n",
    "                count_big[big[left]] -= 1\n",
    "                if count_big.get(big[left], 0) < count_small.get(big[left], 0):\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "        if min_len != float('inf'):\n",
    "            res.append(start)\n",
    "            res.append(start + min_len - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "      helper = collections.defaultdict(int)\n",
    "      for s in small:\n",
    "          helper[s] += 1\n",
    "      n = len(big)\n",
    "      if n<len(small):\n",
    "        return []\n",
    "      elif n==len(small):\n",
    "        return [0,n-1] if small == big else []\n",
    "      helpcounter = len(small)\n",
    "      j = 0\n",
    "      res = (0, n)\n",
    "      for i, num in enumerate(big):\n",
    "          if helper[num] > 0:\n",
    "              helpcounter -= 1\n",
    "          helper[num] -= 1\n",
    "          if helpcounter == 0:\n",
    "              while helper[big[j]] != 0:\n",
    "                  helper[big[j]] += 1\n",
    "                  j += 1\n",
    "              if res[1] - res[0] > i - j:\n",
    "                  res = (j, i)\n",
    "              helper[big[j]] += 1\n",
    "              helpcounter += 1\n",
    "              j += 1\n",
    "      return [] if res[1]==n else [res[0], res[1]]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        target,need=Counter(small),Counter(small)\n",
    "        counter=Counter()\n",
    "        slow,res=0,[]\n",
    "        for i,num in enumerate(big):\n",
    "            counter[num]+=1\n",
    "            if need[num]:\n",
    "                need[num]-=1\n",
    "                if not need[num]:\n",
    "                    need.pop(num)\n",
    "            if not need:\n",
    "                while counter[big[slow]]>target[big[slow]]:\n",
    "                    counter[big[slow]]-=1\n",
    "                    slow+=1\n",
    "                if not res or i-slow<res[1]-res[0]:\n",
    "                    res=[slow,i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "########## 滑窗 #############\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        import collections\n",
    "        cnt = collections.Counter(small)\n",
    "        print(f'cnt:{cnt}')\n",
    "        l = 0\n",
    "        n = 0\n",
    "        ans = []\n",
    "        for r,ch in enumerate(big):\n",
    "            if ch not in cnt:   #不在cnt 继续\n",
    "                continue\n",
    "            cnt[ch] -= 1         #在cnt\n",
    "            if cnt[ch] == 0:\n",
    "                n += 1          #统计n\n",
    "            while big[l] not in cnt or cnt[big[l]] < 0: #移动左指针：big[l]不在cnt，或者big[l]出现不止一次\n",
    "                if cnt[big[l]] < 0:\n",
    "                    cnt[big[l]] += 1    #如果出现不止一次， 左指针右移，并加一\n",
    "                # print(f'-- cnt:{cnt}')\n",
    "                l += 1\n",
    "            if n == len(cnt):          #如果符合题目条件：\n",
    "                if not ans or (ans[1]-ans[0]) > r - l:   #找最小串\n",
    "                    ans = []\n",
    "                    ans.append(l)\n",
    "                    ans.append(r)\n",
    "        return ans\n",
    "\n",
    "# 作者：yang-fan-10\n",
    "# 链接：https://leetcode.cn/problems/shortest-supersequence-lcci/solution/pythonyi-dong-xie-fa-by-yang-fan-10/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import * \n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        dir = {}\n",
    "        for i in small:\n",
    "            dir[i] = []\n",
    "        # 记录big中存在于small中的数的索引\n",
    "        for i in range(len(big)):\n",
    "            if big[i] in dir.keys():\n",
    "                dir[big[i]].append(i)\n",
    "        # 若big不包含全部数字\n",
    "        for i in dir.values():\n",
    "            if i == []:\n",
    "               return []\n",
    "        # 找到len(small)个dir中数组的最小包含区间即为所求\n",
    "        # 使用小顶堆进行查找\n",
    "        heap = []\n",
    "        temp = left = right = 0\n",
    "        fl = fr = 0\n",
    "        dis = float('inf')\n",
    "        for i in dir.keys():\n",
    "            right = max(right,dir[i][0])\n",
    "            heap.append((dir[i][0],temp,0))\n",
    "            temp += 1\n",
    "        heapify(heap)\n",
    "        print(right)\n",
    "        while heap:\n",
    "            (num,id,index) = heappop(heap)\n",
    "            left = num\n",
    "            # 更新区间\n",
    "            if dis > right - left:\n",
    "                fl,fr = left,right\n",
    "                dis = fr - fl\n",
    "            # 当最小值为数组末尾时停止遍历\n",
    "            if index + 1 >= len(dir[small[id]]):\n",
    "                break\n",
    "            # 更新最大值\n",
    "            right = max(right,dir[small[id]][index + 1])\n",
    "            # 将新值放入小顶堆\n",
    "            heappush(heap,(dir[small[id]][index + 1],id,index + 1))\n",
    "        return [fl,fr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        pos = collections.defaultdict(list)\n",
    "        smallSet = set(small)\n",
    "\n",
    "        for i, n in enumerate(big):\n",
    "            if n in smallSet:\n",
    "                pos[n].append(i)\n",
    "        if len(pos) < len(small):\n",
    "            return []\n",
    "\n",
    "        minLen = len(big) + 1\n",
    "\n",
    "        while len(pos) == len(small):\n",
    "            i = min(pos[n][0] for n in small)\n",
    "            j = -1\n",
    "            for n in small:\n",
    "                index = bisect.bisect_left(pos[n], i)\n",
    "                if pos[n][index] > j:\n",
    "                    j = pos[n][index]\n",
    "                if pos[n][index] == i:\n",
    "                    pos[n].pop(0)\n",
    "                    if len(pos[n]) == 0:\n",
    "                        pos.pop(n)\n",
    "\n",
    "            if j - i + 1 < minLen:\n",
    "                minLen = j - i + 1\n",
    "                ans = [i, j]\n",
    "\n",
    "        if minLen <= len(big):\n",
    "            return ans\n",
    "        else:\n",
    "            return []\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], _small: List[int]) -> List[int]:\n",
    "        small = set(_small)\n",
    "        cnt = defaultdict(list)\n",
    "        for i,v in enumerate(big):\n",
    "            if v in small:\n",
    "                cnt[v].append(i)\n",
    "        \n",
    "        if len(cnt)<len(small):\n",
    "            return []\n",
    "        #print(cnt)\n",
    "        ans = [100000,0,0]\n",
    "        p = [0]*len(cnt)\n",
    "        while True:\n",
    "            try:\n",
    "                tmp = [lst[p[i]] for i,lst in enumerate(cnt.values())]\n",
    "            except:\n",
    "                return ans[1:]\n",
    "            Min,Max = min(tmp),max(tmp)\n",
    "            if Max-Min<ans[0]:\n",
    "                ans = [Max-Min, Min, Max]\n",
    "            for i,t in enumerate(tmp):\n",
    "                if t==Min:\n",
    "                    break\n",
    "            p[i] += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        hashMap = collections.defaultdict(int)\n",
    "        needLength = len(small)\n",
    "        for i in small:\n",
    "            hashMap[i] += 1\n",
    "        res = [0, float('inf')]\n",
    "\n",
    "        left = 0\n",
    "        for right, c in enumerate(big):\n",
    "            if hashMap[c] > 0:\n",
    "                needLength -= 1\n",
    "            hashMap[c] -= 1\n",
    "            if needLength == 0:\n",
    "                while True:\n",
    "                    if hashMap[big[left]] == 0:\n",
    "                        break\n",
    "                    hashMap[big[left]] += 1\n",
    "                    left += 1\n",
    "                if right - left < res[1] - res[0]:\n",
    "                    res = [left, right]\n",
    "                hashMap[big[left]] += 1\n",
    "                needLength += 1\n",
    "                left += 1\n",
    "\n",
    "        return [] if res[1] > len(big) else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "                \n",
    "        res = []\n",
    "        length = 9999999\n",
    "        import collections\n",
    "        hs = collections.Counter(small)\n",
    "        left = right = 0\n",
    "        count = len(small)\n",
    "        while right<len(big):\n",
    "            if hs[big[right]] >0:\n",
    "                count-=1\n",
    "            hs[big[right]]-=1\n",
    "\n",
    "            if count==0: # 缩短左边界\n",
    "                while True:\n",
    "                    if hs[big[left]] ==0:\n",
    "                        break\n",
    "                    hs[big[left]]+=1\n",
    "                    left+=1\n",
    "                if length>right-left:\n",
    "                    length  = right-left\n",
    "                    res = [left,right]\n",
    "\n",
    "                hs[big[left]]+=1\n",
    "                left +=1\n",
    "                count+=1\n",
    "            right+=1\n",
    "        print(res)\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        hashmap = defaultdict(int)\n",
    "        diff = 0\n",
    "        for a in small:\n",
    "            hashmap[a] += 1\n",
    "            diff += 1\n",
    "        start = 0\n",
    "        ans = []\n",
    "        for j, b in enumerate(big):\n",
    "            if hashmap[b] > 0:\n",
    "                diff -= 1\n",
    "            hashmap[b] -= 1\n",
    "            if diff == 0:\n",
    "                while 1:\n",
    "                    if hashmap[big[start]] >= 0:\n",
    "                        break\n",
    "                    hashmap[big[start]] += 1\n",
    "                    start += 1\n",
    "                if ans == [] or j - start < ans[-1] - ans[0]:\n",
    "                    ans = [start, j]\n",
    "                hashmap[big[start]] += 1\n",
    "                start += 1\n",
    "                diff += 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        from collections import Counter\n",
    "        import sys\n",
    "        cnt = Counter(small)\n",
    "        need_tobe_find = len(small)\n",
    "        i = left = 0\n",
    "        minLen = sys.maxsize\n",
    "        findFlag=False\n",
    "        while i < len(big):\n",
    "            if cnt[big[i]] >0:\n",
    "                need_tobe_find -= 1\n",
    "            cnt[big[i]] -= 1\n",
    "            while need_tobe_find == 0:\n",
    "                findFlag =True\n",
    "                tmp = i - left + 1\n",
    "                if tmp < minLen:\n",
    "                    minLen = tmp\n",
    "                    res = [left, i]\n",
    "                if cnt[big[left]] == 0:\n",
    "                    need_tobe_find += 1\n",
    "                cnt[big[left]] += 1\n",
    "                left += 1\n",
    "            i += 1\n",
    "        if findFlag:\n",
    "            return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:\n",
    "        l, r, c, res = 0, 0, collections.Counter(), []\n",
    "        if set(small)-set(big) != set(): return []\n",
    "        while r<len(big):\n",
    "            while r<len(big) and any(i not in c for i in small):\n",
    "                c[big[r]] += 1\n",
    "                r += 1 \n",
    "            while all(i in c for i in small):\n",
    "                if c[big[l]] == 1: c.pop(big[l])\n",
    "                else: c[big[l]] -= 1\n",
    "                l += 1\n",
    "            res.append([l-1, r-1])\n",
    "        return sorted(res, key=lambda x:(x[1]-x[0], x[0]))[0]\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
